使用迭代替代

Question

我试图使用迭代替换找到以下复发的运行时查找多次复发的运行时间：

T(n) = T(n/2) + T(n/3) + n 

的问题是，有两个T(n/x)条款和发现的一般形式，这种情况有被证明是相当有挑战性的。 有没有一个通用的指导方针应该使用这种情况下的迭代替换？

Answer 1

这个重复是来自Akra–Bazzi重复发生的类。以下公式的解决方案是：

另外，假设T(1) = c0那么你能证明T(n) <= max(6,c0)*n感应。

您也可以使用替代规则。具体方法如下：

T(n) = T(n/2)+T(n/3) + n = 
= n+(n/2+n/3)+T(n/(2*2))+T(n/(2*3))+T(n/(3*2))+T(n/(3*3)) 
= n+(n/2+n/3)+(n/(2*2)+n/(2*3)+n/(3*2)+n/(3*3)) 
      +T(n/(2*2*2))+T(n/(2*2*3)) 
      +T(n/(2*3*2))+T(n/(2*3*3)) 
      +T(n/(3*2*2))+T(n/(3*2*3)) 
      +T(n/(3*3*2))+T(n/(3*3*3))= 
... 
= n * (1 + 5/6 + (5/6)^2 + (5/6)^3 + (5/6)^4 + ...) 
= 6 * n (assuming n = 2^k3^k. you get < 6*n otherwise) 

Answer 2

没有正式在这里，但

T(n) = 2T(n/2) + n // O(nlog(n)) 

所以你的复发可能仍然是O（n日志（n））的？

又是什么基本情况？