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

我一直在尝试用递归树方法来解决问题，通常我们可以找到水平和，得到一个GP，然后我们可以应用无穷的GP和，从而得到它的最终大O值。
对于水平和相同的情况我们该怎么办-
t（n）=3t（n/3）+cn
下面的答案是Theta（nlogn）

最佳答案

首先，让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＝3 ^ k，树是平衡的，并且具有k＝Log3n高度，因此复杂性是θ（n*Log3n）。

关于algorithm - 级别总和相同时的递归树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54376963/