2

私は Sedgewick と Flajolet による「アルゴリズムの分析」を読んでいます。

ここに画像の説明を入力

そして、その証明を以下に示します。ここに画像の説明を入力

O(N) がどこに行くのか、誰か説明できますか? Cn が O(NlogN) であることを証明するからです。

4

2 に答える 2

3

あなたが正しい; 私を超えた理由で、彼らは実際に証明したよりも多くの定理を述べま​​した。残りを埋める 1 つの方法を次に示します。

補題整数 n >= 1 の T(n) を次のように定義するとします。

T(n) = 0,                                for n = 1;
       T(floor(n/2)) + T(ceil(n/2)) + n, for n > 1.

次に、整数 n >= 1 の場合、T(n) <= n lg n + n - 1 = n lg n + O(n) です。

帰納法による証明。n = 1 の場合、T(1) = 0 = 1 lg 1 + 1 - 1. n > 1 の場合、2 つのケースがあります。n が偶数の場合、

T(n)  = 2T(n/2) + n
     <= 2(n/2) lg(n/2) + 2n/2 - 2 + n
      = n (lg n - 1) + 2n - 2
     <  n lg n + n - 1.

n が奇数の場合、事態は複雑になります。

T(n)  = T(n/2 - 1/2) + T(n/2 + 1/2) + n
     <=   (n/2 - 1/2) lg(n/2 - 1/2) + (n/2 - 1/2) - 1
        + (n/2 + 1/2) lg(n/2 + 1/2) + (n/2 + 1/2) - 1
        + n
      = (n/2 - 1/2) lg(n/2 - 1/2) + (n/2 + 1/2) lg(n/2 + 1/2) + 2n - 2.

2 つの醜い項はどちらも (n/2) lg(n/2) に近いので、それぞれをその量に誤差項を加えたものとして書きます。

T(n) <= (n/2 - 1/2) lg(n/2 - 1/2) + (n/2 + 1/2) lg(n/2 + 1/2) + 2n - 2
      =   (n/2) lg(n/2) + ((n/2 - 1/2) lg(n/2 - 1/2) - (n/2) lg(n/2))
        + (n/2) lg(n/2) + ((n/2 + 1/2) lg(n/2 + 1/2) - (n/2) lg(n/2))
        + 2n - 2
      =   n lg(n/2) + 2n - 2
        + (n/2 - 1/2) lg(n/2 - 1/2) - (n/2) lg(n/2)
        + (n/2 + 1/2) lg(n/2 + 1/2) - (n/2) lg(n/2)
      =   n (lg n - 1) + 2n - 2
        + (n/2) (lg(n/2 - 1/2) - lg(n/2)) - (1/2) lg(n/2 - 1/2)
        + (n/2) (lg(n/2 + 1/2) - lg(n/2)) + (1/2) lg(n/2 + 1/2)
      =   n lg n + n - 2
        + (n/2) lg((n/2 - 1/2)/(n/2)) - (1/2) lg(n/2 - 1/2)
        + (n/2) lg((n/2 + 1/2)/(n/2)) + (1/2) lg(n/2 + 1/2)
      =   n lg n + n - 2
        + (n/2) lg(1 - 1/n) - (1/2) lg(n/2 - 1/2)
        + (n/2) lg(1 + 1/n) + (1/2) lg(n/2 + 1/2)
      =   n lg n + n - 2
        + (n/2) lg(1 - 1/n) + (n/2) lg(1 + 1/n)
        + (1/2) lg(n/2 + 1/2) - (1/2) lg(n/2 - 1/2)
      =   n lg n + n - 2
        + (n/2) lg((1 - 1/n) (1 + 1/n))
        + (1/2) lg((n/2 + 1/2) / (n/2 - 1/2))
      =   n lg n + n - 2
        + (n/2) lg(1 - 1/n^2)
        + (1/2) lg(1 + 2/(n - 1)).

項 (n/2) lg(1 - 1/n^2) は負であり、n >= 3 の場合、この場合の最小 n は、項 (1/2) lg(1 + 2/(n - 1)) は最大で 1/2 です。(実際には、T(n) <= n lg n + n/2 - 1/2 であることを示すために、戻って証明をやり直すことができます。これは演習として残しておきます。) したがって、

T(n) <    n lg n + n - 2
        + 0
        + 1
      = n lg n + n - 1.
于 2013-07-13T15:03:55.763 に答える
0

あなたが求めている O(N) がどこで間違っているか、または欠落しているかは正確にはわかりませんが、その分析は特別なケースでは問題ありませんN = 2^n。

(1) の後の数学の最初の行は、特殊なケースの繰り返しを再記述しています。数学ショーの次の長い行

C_{2^n} = (2^n) n

今、私たちは知っ2^n = Nていn = lg Nます。これらの両方で代入すると、

C_N = N lg N

彼らが言うように。質問が正しく表示されない場合は、コメントしてください。

于 2013-07-13T16:51:01.903 に答える