如何找到以下递归关系的时间复杂度？

Question

算法的运行时间由以下递推关系表示；

T(n) = n 如果 n<=3

T(n) = T[n/3] + cn 否则

如何找到这个算法的时间复杂度？

我得到了 big-theta(n) 的单字答案。但我无法弄清楚它是如何被发现的。所以我想知道找到相同的过程。

Answer 1

尝试多次展开重复周期以查看出现的模式可能会有所帮助：

T[n]

= T[n/3] + cn

= T[n/9] + cn / 3 + cn

= T[n/27] + cn / 9 + cn / 3 + cn

= T[n/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 + ...).

那个和就是一个几何级数的和。如果这足以让你破解这个，太好了！如果没有，请打开您友好的社区维基百科并查看那里的公式。

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

Answer 2

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)

Otherwise: You can use Master Theorem also.

Answer 3

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 or k >= log(base 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(base 3)(n/3^3))

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

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

如何找到以下递归关系的时间复杂度？

How to find the Time Complexity of the following Recurrence Relation?

algorithm

time-complexity

recurrence

T(n) = n 如果 n<=3

T(n) = T[n/3] + cn 否则