1

ボトムアップヒープ構築を使用してソートされていない配列からバイナリヒープを生成するための時間の複雑さが O(n) である理由を説明できる人はいますか?

(これまでに見つかった解決策: Thomas と Goodrich の本で、ヒープを構築する際の内部ノードのパスのサイズの合計が 2n-1 であることがわかりましたが、その説明はまだわかりません)

ありがとう。

4

2 に答える 2

9

ソートされていない配列からバイナリ ヒープを生成するための通常の BUILD-HEAP手順は、次のように実装されます。

BUILD-HEAP(A)
 heap-size[A] ← length[A]
  for i ← length[A]/2 downto 1
   do HEAPIFY(A, i)

ここで、HEAPIFYプロシージャは O(h) 時間かかります。ここで、h はツリーの高さであり、実行時間 O(nh) を行う O(n) 回の呼び出しがあります。h=lg n を考慮すると、 BUILD-HEAP手順は O(n lg n) 時間かかると言えます。

より厳密な分析のために、ほとんどのノードの高さが小さいことがわかります。実際、任意の高さ h では、最大で CEIL(n/ (2^h +1)) ノードが存在する可能性があり、これは帰納法によって簡単に証明できます。したがって、BUILD-HEAPの実行時間は次のように記述できます。

lg n                     lg n
∑ n/(2^h+1)*O(h)  = O(n* ∑ O(h/2^h)) 
h=0                      h=0

今、

∞   
∑ k*x^k = X/(1-x)^2
k=0              
               ∞ 
Putting x=1/2, ∑h/2^h = (1/2) / (1-1/2)^2 = 2
               h=0

したがって、実行時間は、

lg n                     ∞   
O(n* ∑ O(h/2^h))  = O(n* ∑ O(h/2^h))  = O(n)
h=0                      h=0

したがって、これにより O(n) の実行時間が得られます。

注: 分析はこれから取得されます。

于 2012-05-18T12:18:34.420 に答える
2

ウィキペディアをチェックしてください：

ヒープの構築: 連続した挿入によってヒープを構築できます。各挿入には O(log n) の時間がかかり、n 個の要素があるため、このアプローチには O(n log n) の時間が必要です。ただし、これは最適な方法ではありません。最適な方法は、形状プロパティを考慮して、要素を二分木に任意に配置することから始まります。次に、最下位レベルから開始して上に移動し、ヒープ プロパティが復元されるまで、削除アルゴリズムのように各サブツリーのルートを下にシフトします。

http://en.wikipedia.org/wiki/Binary_heap

于 2012-05-18T01:41:49.930 に答える