1

いくつかのことを確認したかったのですが、以下の手順を実行しましたか？

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<c<= 1

cn+nを組み合わせる特別な理由はありますか。その背後にあるロジックを見ることができますが、そのステップを実行する必要がありますか？それなら私はどんな場合でもそれをすることができるので...それは少し奇妙です..

4

1 に答える 1

1

あなたはまだ正しかった：

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

にとってΩ(nlogn)

これは、c <= 0の場合にのみ成立するため、c>=0という仮定と矛盾します。

2番目の証明を修正する1つの方法は次のとおりです。

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

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

一般に、下限と上限の値はそれほど重要ではありません。目標は、次のような2つの定数を見つけるc1ことc2です。

c1*n*logn <= T(n) <= c2*n*lognforall n >= some n0。

于 2012-03-03T20:33:43.910 に答える