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

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 + ...).

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

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