代替方法

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 

私は私がCの私の範囲のために終わったことだったステップに問題を抱えている：上限 下限

用= 1 0 < C <ため

C> = 1

cn + nを組み合わせる特別な理由はありますか？私はそれの背後にある論理をある程度見ることができますが、そのステップを実行する必要がありますか？その後、私はのためにそれを行うことができますので、あなたがた

Answer 1

ビット奇妙ですいずれにせよ... ..のような、まだ右まで：

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

それが唯一のC <のために保持しているためΩ(nlogn)

用= 0私たちの仮定と矛盾すること、C> =第二の証明を修正する0

一つの方法は次のようになります。

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

したがって：T(n) = Ω(nlogn)。

一般に、下限と上限の値はあまり重要ではありません。目標は、

c1*n*logn <= T(n) <= c2*n*logn forall n >= some n0のような2つの定数c1とc2を見つけることです。