7

n個の要素のバイナリヒープがあり、さらにn個の要素を挿入したいとします（必ずしも次々に挿入する必要はありません）。これに必要な合計時間はどれくらいですか？

1回の挿入でlognが必要になるため、シータ（n logn）だと思います。

4

3 に答える 3

6

given : n 個の要素のヒープと、さらに n 個の要素が挿入されます。したがって、最終的には 2*n 要素になります。ヒープは2つの方法で作成できるため、1.連続挿入と2.ヒープの構築方法。これらのビルド ヒープ メソッドの中で、ヒープを構築するのに O(n) 時間かかり ます。. したがって、必要な合計時間は O(2*n) であり、これは O(n) と同じです

于 2013-01-23T04:59:53.860 に答える
4

与えられたと仮定します：

  • 標準バイナリ ヒープHによって実装されたプライオリティ キュー(配列上に実装)
  • nヒープの現在のサイズ

次の挿入プロパティがあります。

  • W(n) = ワーストケース(n) = Θ(lg n) (シータ)。-> W(n)=Ω(lg n) および W(n)=O(lg n)
  • A(n) = AverageCase(n) = Θ(lg n) (シータ)。-> W(n)=Ω(lg n) および W(n)=O(lg n)
  • B(n) = BestCase(n) = Θ(1) (シータ)。-> W(n)=Ω(1) および W(n)=O(1)

したがって、すべてのケースについて、

  • T(n) = Ω(1) および T(n) = O(lg n)

最悪の場合は、新しい最小値を挿入するため、アップヒープはブランチ全体を移動する必要があります。

BestCase は、minimal-heap (最上位に最小のヒープ) の場合に、BIG (更新されたブランチで最大) 値を挿入する場合です (したがって、up-heap はすぐに停止します)。

すでに n 個の要素を含むヒープでの一連の n 操作について質問しましたが、サイズは大きくなります

from n to 2*n

漸近的には...

n=Θ(n)
2*n=Θ(n)

方程式を単純化するもの。( nの成長は一定の係数によるものであるため、心配する必要はありません)。

したがって、「n回の挿入」操作があります。

  • Xi(n) = X_for_n_insertions(n)
    • Wi(n) = Θ(n lg n)
    • Ai(n) = Θ(n lg n)
    • Bi(n) = Θ(n)
  • それは、「すべてのケース」に対して次のことを意味します。
    • Ti(n) = Ω(n) および Ti(n) = O(n lg n)

PS Theta Θ 、 Omega Ω 記号を表示するには、UTF-8 がインストールされている/互換性がある必要があります。

于 2012-01-09T15:06:24.423 に答える
1

theeta(nlogn) ではありません... その順序 (nlogn) は、一部の挿入が正確な logn 時間よりも短い時間で済むためです... したがって、n 個の挿入の場合、<=nlogn に時間がかかります

=> 時間計算量=O(nlogn)

于 2011-12-28T13:08:33.413 に答える