替代方法

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。