702

ヒープの構築がO(n)の複雑さになる方法を誰かが説明できますか?

アイテムをヒープに挿入するのはO(log n)であり、挿入は n/2 回繰り返されます (残りは葉であり、ヒープ プロパティに違反することはできません)。したがって、これは複雑さがO(n log n)であることを意味します。

言い換えれば、「ヒープ化」する各項目について、これまでのヒープのレベル ( log nレベル) ごとに 1 回フィルター ダウン (ふるい分け) する必要がある可能性があります。

私は何が欠けていますか？

4

16 に答える 16

354

あなたの分析は正しいです。ただし、タイトではありません。

ヒープの構築が線形操作である理由を説明するのは簡単ではありません。よく読んだほうがよいでしょう。

アルゴリズムの優れた分析は、ここで見ることができます。

主な考え方は、build_heapアルゴリズムでは実際のheapifyコストがO(log n)すべての要素にかかるわけではないということです。

が呼び出されたときheapifyの実行時間は、プロセスが終了する前に要素がツリー内でどれだけ下に移動するかによって異なります。つまり、ヒープ内の要素の高さに依存します。最悪の場合、要素がリーフ レベルまで下がってしまうこともあります。

レベルごとに行われた作業を数えてみましょう。

一番下のレベルには2^(h)ノードがありますが、これらのいずれも呼び出していないheapifyため、作業は 0 です。次のレベルには2^(h − 1)ノードがあり、それぞれが 1 レベルずつ下に移動する可能性があります。下から 3 番目のレベルに2^(h − 2)ノードがあり、それぞれが 2 レベルずつ下に移動する可能性があります。

すべての heapify 操作O(log n)がO(n).

于 2012-03-18T03:39:26.430 に答える
114

直感的に:

「複雑さは O(nLog n) である必要があります...「ヒープ化」するアイテムごとに、これまでのヒープの各レベル (log n レベル) に対して 1 回フィルターダウンする必要がある可能性があります。

そうではありません。あなたのロジックは厳密な境界を生成しません-各ヒープ化の複雑さを過大評価します。ボトムアップで構築した場合、挿入 (heapify) は よりもはるかに少なくなる可能性がありO(log(n))ます。プロセスは次のとおりです。

( ステップ 1 ) 最初のn/2要素は、ヒープの一番下の行に配置されます。h=0であるため、heapify は必要ありません。

( ステップ 2 ) 次の要素は、行 1 の下から上に移動します。、heapify フィルターを 1 レベル下げます。n/22h=1

( ステップi ) 次の要素は、下から上に並んでいます。、heapify フィルターのレベルが下がります。n/2iih=ii

( Step log(n) ) 最後の要素が下から上に並んでいます。、heapify フィルターのレベルが下がります。n/2log2(n) = 1log(n)h=log(n)log(n)

注意:ステップ 11/2の後、要素のうちの 1 つ(n/2)が既にヒープにあり、heapify を 1 回呼び出す必要さえありませんでした。また、1 つの要素 (ルート) だけが実際に完全なlog(n)複雑さを引き起こしていることに注意してください。

理論的には:

Nサイズ のヒープを構築するための合計ステップはn、数学的に書き出すことができます。

heightで、 heapify を呼び出す必要iがある要素があることを (上で) 示しました。高さでの heapifyは です。これは与える：n/2i+1iO(i)

ここに画像の説明を入力

最後の総和の解は、よく知られている等比級数方程式の両辺の導関数をとることによって見つけることができます。

ここに画像の説明を入力

最後にx = 1/2、上記の式に代入すると、 が得られ2ます。これを最初の式に代入すると、次のようになります。

ここに画像の説明を入力

したがって、ステップの総数はO(n)

于 2013-08-18T03:13:59.733 に答える
46

要素を繰り返し挿入してヒープを構築すると、O(n log n) になります。ただし、要素を任意の順序で挿入し、アルゴリズムを適用して適切な順序に「ヒープ化」することにより、新しいヒープをより効率的に作成できます (もちろん、ヒープの種類によって異なります)。

例については、 http://en.wikipedia.org/wiki/Binary_heapの「ヒープの構築」を参照してください。この場合、ヒープ条件が満たされるまで親ノードと子ノードを交換しながら、基本的にツリーの最下位レベルから作業を進めます。

于 2012-03-18T03:36:33.963 に答える
11

ヒープを構築する際に、ボトムアップのアプローチを取っているとしましょう。

  1. 各要素を取得し、その子と比較して、ペアがヒープ ルールに準拠しているかどうかを確認します。したがって、リーフは無料でヒープに含まれます。それは彼らに子供がいないからです。
  2. 上に移動すると、葉のすぐ上のノードの最悪のシナリオは 1 回の比較になります (最大で、1 世代の子のみと比較されます)。
  3. さらに上に移動すると、直接の親は最大で 2 世代の子供と比較できます。
  4. 同じ方向に進むと、最悪のシナリオではルートの log(n) 比較が行われます。直接の子は log(n)-1、直接の子は log(n)-2 などです。
  5. 以上をまとめると、log(n) + {log(n)-1}*2 + {log(n)-2}*4 + ..... + 1*2^{( logn)-1} は O(n) に他なりません。
于 2012-07-03T10:44:33.163 に答える
2

ヒープを構築する場合、高さ logn -1 (logn は n 要素のツリーの高さ) から開始します。高さ 'h' に存在する各要素について、最大で (logn -h) 高さを下げます。

    So total number of traversal would be:-
    T(n) = sigma((2^(logn-h))*h) where h varies from 1 to logn
    T(n) = n((1/2)+(2/4)+(3/8)+.....+(logn/(2^logn)))
    T(n) = n*(sigma(x/(2^x))) where x varies from 1 to logn
     and according to the [sources][1]
    function in the bracket approaches to 2 at infinity.
    Hence T(n) ~ O(n)
于 2015-08-20T09:26:53.170 に答える
1

連続挿入は、次のように記述できます。

T = O(log(1) + log(2) + .. + log(n)) = O(log(n!))

n! =~ O(n^(n + O(1)))したがって、スターリング近似により、 、T =~ O(nlog(n))

これが役に立てば幸いです。最適な方法O(n)は、特定のセットに対してビルド ヒープ アルゴリズムを使用することです (順序は関係ありません)。

于 2013-09-14T10:45:28.877 に答える
1

基本的に、作業はヒープの構築中に非リーフノードでのみ行われます...そして行われる作業は、ヒープ条件を満たすためにスワップダウンする量です...つまり、(最悪の場合)量は高さに比例しますノードの...全体として、問題の複雑さはすべての非葉ノードの高さの合計に比例します..これは(2^h+1 - 1)-h-1=nh-1=ですの上）

于 2015-05-31T20:15:54.317 に答える
0

Jeremy west による説明が本当に好きです.... 理解しやすい別のアプローチがここにあり ます http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

したがって、buildheap は heapify に依存し、すべてのノードの高さの合計に依存する shiftdown アプローチが使用されます。したがって、(2^i*(hi)) の i = 0 から i = h までの S = 合計によって与えられるノードの高さの合計を見つけるには、ここで、h = logn は s を解くツリーの高さです。 s = 2^(h+1) - 1 - (h+1) なので、 n = 2^(h+1) - 1 s = n - h - 1 = n- logn - 1 s = O(n),したがって、ビルドヒープの複雑さは O(n) です。

于 2014-05-26T09:19:29.583 に答える
0

「ビルド ヒープの線形時間境界は、ヒープ内のすべてのノードの高さの合計を計算することで表示できます。これは破線の最大数です。N = 2^( を含む高さ h の完全なバイナリ ツリーの場合、 h+1) – 1 ノード、ノードの高さの合計は N – H – 1 です。したがって、O(N) です。」

于 2015-01-15T01:17:54.563 に答える