问如何求出下列递推关系的时间复杂度？

EN

试着重复几次，看看会出现什么样的模式可能会有帮助：

总氮 = Tn/3 + cn = Tn/9 + cn /3+ cn = Tn/27 + cn /9+ cn /3+ cn = Tn/81 + cn / 27 + cn /9+ cn /3+ cn

更广泛地说，这种重复似乎是为了

cn + cn /3+ cn /9+ cn / 27 + cn / 81 + = cn(1 + 1/3 + 1/9 + 1/27 + 1/81 +.)

这个和是一个几何级数的和。如果这足以让你破解这个，那就太好了！如果没有，就把你的友好邻里维基百科拉起来，看看那里的公式。

上面的策略在这种情况下效果很好，但是对于更一般的递归，使用主定理通常是有帮助的，它可以立即解决许多像这样的递归。请查看维基百科，了解关于这个定理的详细信息以及如何使用它。

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

或T(n/3^2) + cn/3 + cn

或T(n/3^3) + cn/3^2 + cn/3 + cn

诸若此类

最后T(n) = T(n/3^k) + cn/3^(k-1) + cn/3^(k - 2) .cn/3 + cn . (1)

现基箱

n/3^k <= 3或k >= log(基3) (n/3)，为了简单起见，只考虑等式

所以方程式1会变成

T(n) =n+ cn/3^(k-1) +cn/3^(k-2).cn/3 + cn

或n+ cn(1 + 1/3 + 1/3^2 ....+ 1/3^(k-1) )，即GP

或n+ cn (1.(1 - 1/3^(k-2))/(1-1/3))

或n+ cn((3^(k-1)- 3) /2.3^(k-2)

将k的值放入上述方程中

N+ cn((3^(log(base 3) (n / 3^2)) /(2.3^)(log(基3)(n/3^3))

它最终给出n+ (3/2)cn

或T(n) = n(1+(3/2) c)，即Theta(n)

T(n) = cn + T(n/3)
     = cn + cn/3 + T(n/9)
     = cn + cn/3 + cn/9 + T(n/27)
Taking the sum of infinite GP series. The value of T(n) will
be less than this sum.
T(n) <= cn(1/(1-1/3))
     <= 3cn/2

or we can say 
cn <= T(n) <= 3cn/2
Therefore T(n) = \theta(n)

否则:你也可以使用主定理。