1

「アルゴリズムの紹介」には次のような問題があります: (4.4-6)

が定数であるT(n) = T(n/3) + T(2*n/3) + cn
場合の再帰の解は、再帰木に訴えてΩ(n log 2 n) であると主張します。c

再帰ツリーを使用すると、最終的に. それを示す次のステップがわかりません。私もそれ をグーグルで検索しましたが、どういうわけか答えに何か問題があると感じています。T(N) >= n log3n
T(N) >= n log2n
T(N) >= n log3nT(N) >= n log2nlog3nlog2n

4

2 に答える 2

0

大きなオメガ:f(n)の定義Omega(g(n))を思い出してfくださいg。または、もっと数学的にしたい場合：

ビッグオメガの定義

f(n) = n * log_3(n)と を定義しましょうg(n) = n * log_2(n)。

ここで、 となる定数を見つけることができれば、cそれf(n) > c * g(n)が にあることが示されf(n)ましたOmega(g(n))。

    log_3(n) = log_2(n) / log_2(3)
    log_2(3) ~= 1.585 < 2
=>  log_3(n) > 2 * log_2(n)
=>  n * log_3(n) > 2 * n * log_2(n)
=>  f(n) > c * g(n)

の選択した値に対してc = 2(もちろん、c > log_2(3).

于 2013-07-04T10:59:09.127 に答える