algorithm - 级别和相同时的递归树

Question

我一直在尝试使用递归树方法解决问题，通常我们可以找到水平总和并获得一个 GP，然后我们可以在其中应用无限 GP 总和，从而获得它的最终 Big-O 值。

对于具有相同水平总和的情况，我们该怎么办，例如 -

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

以下的答案是 Theta(nlogn)

标签： algorithmrecursionbig-orecurrence

Answer 1

首先，让 T(1)=1，n=3^k 和 c=1：

  T(n)   = 3T(n/3) + cn
= T(3^k) = 3T(3^(k-1)) + 3^k
         = 3(3T(3^(k-2)) + 3^(k-1)) + 3^k
         = 3^2T(3^(k-2)) + 3^k + 3^k
         = 3^2(3T(3^(k-3)) + 3^(k-2)) + 3^k + 3^k
         = 3^3T(3^(k-3)) + 3^k + 3^k + 3^k
         = ...
         = 3^kT(1) + k*3^k 
         = nT(1) + n*log3n
         = n + n*log3n

你能从这里用归纳法证明吗？

@编辑

考虑以下树扩展：

                    n                     = n
    n/3            n/3            n/3     = n
n/9 n/9 n/9    n/9 n/9 n/9    n/9 n/9 n/9 = n
                   ...                    = n

每行总和为 n。如果假设 n=3^k，则树是平衡的并且具有 k=log3n 高度，因此复杂度为 Theta(n*log3n)。