algorithm - 替代方法

我只是想验证一些事情我做了下面的步骤对吗？

T(n)   = 3T(n/3) + n  : Theta(nlogn)

O(nlogn)

T(k)   = cklog(k)  k<n

T(n/4) = c(n/3)log(n/3)
       = c(n/3)[logn - log3]
       = c(n/3)logn - c(n/3)log3

T(n)   = cnlogn-cnlog3 + n

       <= cnlogn -cn + n
       <= cnlogn -dn **[STEP A]**
       <= cnlogn if c >= d

Omega(nlogn)
   >= cnlogn -cn + n
   >= cnlogn -dn **[STEP A]**
   >= cnlogn if 0 < c <= d

我在步骤a上遇到了问题，我的c范围的结果是：
上界c>=1
下界为0有没有一个特殊的原因让你把cn+n结合起来，我可以看出它背后的逻辑，但有必要这样做吗？因为那样我就可以像任何情况一样…这有点奇怪。。

最佳答案

直到：

T(n) = cnlogn-cnlog3 + n
     >= cnlogn -cn + n

对于Ω(nlogn)
因为它只适用于c=0相矛盾。
修复第二个证据的一种方法是：

T(n) = cnlogn - cnlog3 + n
     = cnlogn - n(clog3 - 1)
     <= cnlogn when c >= 1/log3

因此：T(n) = Ω(nlogn)。
一般来说，下限值和上限值无关紧要目标是找到两个常数c1和c2，以便：
对于所有c1*n*logn <= T(n) <= c2*n*logn。

关于algorithm - 替代方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9547494/