4

背景

ウィキペディアや私が見つけた他の情報源によると、空のバイナリヒープから始めてn個の要素を挿入することでn個の要素のバイナリヒープを構築するのはO（n log n）です。これは、バイナリヒープの挿入がO（log n）だからです。そしてあなたはそれをn回やっています。これを挿入アルゴリズムと呼びましょう。

また、要素の前半/上半分をシンク/トリクルダウン/パーコレーションダウン/カスケードダウン/ヒープダウン/バブルダウンする別のアプローチも示します。これは、中央の要素から始まり、最初の要素で終わります。 O（n）、はるかに優れた複雑さ。この複雑さの証拠は、各要素のシンクの複雑さがバイナリヒープ内の高さに依存するという洞察に基づいています。それが下部に近い場合、それは小さく、おそらくゼロになります。上部に近い場合は、大きくなる可能性があります。おそらくlognです。重要なのは、このプロセスで沈められたすべての要素の複雑さがlog nではないため、全体的な複雑さはO（ n log n ）よりもはるかに小さく、実際にはO（n）。これをシンクアルゴリズムと呼びましょう。

質問

同じ理由で、挿入アルゴリズムの複雑さがシンクアルゴリズムの複雑さと同じではないのはなぜですか？

挿入アルゴリズムの最初のいくつかの要素に対して行われた実際の作業を検討してください。最初の挿入のコストはlognではなく、ゼロです。これは、バイナリヒープが空であるためです。2番目の挿入のコストは最悪の場合1スワップであり、4番目の挿入のコストは最悪の場合2スワップであり、以下同様です。要素を挿入する実際の複雑さは、バイナリヒープの現在の深さに依存するため、ほとんどの挿入の複雑さはO（log n ）未満です。n個の要素がすべて挿入されるまで、挿入コストは技術的にはO（log n）に達しません[最後の要素の場合はO（log（ n -1））です]。

これらの節約は、シンクアルゴリズムによって得られる節約と同じように聞こえますが、なぜ両方のアルゴリズムで同じようにカウントされないのでしょうか。

4

4 に答える 4

5

実際には、n=2^x - 1 (最下位レベルがいっぱい) の場合、挿入アルゴリズムで (葉ノードになるために) n/2 要素が log(n) スワップを必要とする場合があります。したがって、葉のみに (n/​​2)(log(n)) スワップが必要になります。これにより、すでに O(nlogn) になります。

もう 1 つのアルゴリズムでは、log(n) スワップが必要な要素は 1 つだけ、log(n)-1 スワップが必要な要素は 2 つ、log(n)-2 スワップが必要な要素は 4 つなどです。対数の代わりに定数。

于 2013-01-20T06:24:40.323 に答える
1

直感的には、シンク アルゴリズムは数個のもの (ヒープ/ツリーの最上部にある小さなレイヤーにあるもの) のみを移動しますが、挿入アルゴリズムは多くのもの (ヒープ/ツリーの最下部にある大きなレイヤーにあるもの) を移動します。ヒープ) 距離 log(n)。

シンク アルゴリズムがこれを回避できる理由についての直感は、挿入アルゴリズムも追加の (適切な) 要件を満たしているということです。挿入を任意の時点で停止する場合、部分的に形成されたヒープは有効なヒープでなければなりません (そして有効なヒープです)。シンク アルゴリズムの場合、得られるのはヒープの奇妙で不正な下部部分だけです。松の木のてっぺんが切り取られたようなものです。

また、合計と何とか何とか。たとえば、サイズ n の任意の大きなセットの要素の後半を挿入するとどうなるかについて、漸近的に考えるのが最善です。

于 2013-01-22T07:07:01.413 に答える
1

log(n-1) が log(n) よりも小さいのは事実ですが、違いを生むほど小さくはありません。

数学的に: i 番目の要素を挿入する最悪の場合のコストは ceil(log i) です。したがって、要素 1 ～ n を挿入する最悪の場合のコストは、sum(i = 1..n, ceil(log i)) > sum(i = 1..n, log i) = log 1 + log 1 + .. . + ログ n = ログ (1 × 2 × ... × n) = ログ n! = O(n log n)。

于 2013-01-21T04:42:32.547 に答える