替代方法

Question

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

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为上限Ç< = 1为下界

是否有一个特殊的原因，你会结合cn + n。我可以看到它背后的逻辑，但有必要这样做吗？因为那时我能做到这一点像任何情况下......这是一个有点怪..

Answer 1

你仍然有可能直到：

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

为Ω(nlogn)

因为它仅拥有对C < = 0这是矛盾与我们的假设，即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 forall n >= some n0。