空の最小ヒープ上でn任意の挿入および削除操作を行う場合 (最小ヒープ内の指定された削除場所で)。挿入O(1)と削除の償却分析はなぜO(log n)ですか?
a) insert O(log n), delete O(1)
b) insert O(log n), delete O(log n)
c) insert O(1), delete O(1)
d) insert O(1), delete O(log n)
誰でも私のためにそれを明確にすることができますか?
5519 次
1 に答える
9
あなたの質問とコメントへの回答に基づいて、バイナリ ヒープを仮定します。
まず、挿入の最悪のケースは O(log n) であり、最小項目の削除の最悪のケースは O(log n) です。これは、ヒープのツリー構造に従います。つまり、n 項目のヒープの場合、ツリーには log(n) レベルがあります。
挿入には、(論理的に) アイテムをツリーの最下部の右端のノードとして追加し、それを必要なレベルまで「バブリング」することが含まれます。新しいアイテムがルートよりも小さい場合、すべてのログ (n) レベルの最上部までバブリングする必要があります。したがって、数字 10、9、8、7、6、5、4、3、2、1 を最小ヒープに挿入すると、すべての挿入で最悪のケースが発生します。
最小の要素を削除するには、最下位のアイテム (ルート) を最後のアイテムに置き換えてから、そのアイテムを適切な位置に「ふるい分け」ます。繰り返しますが、これには最大で log(n) 回の操作が必要になる場合があります。
それは最悪のケースです。平均的なケースは大きく異なります。
バイナリ ヒープでは、ノードの半分がリーフであり、子を持たないことに注意してください。したがって、アイテムをランダムな順序で挿入する場合、挿入するアイテムの半分の時間は最下位レベルに属し、「バブルアップ」する必要はありません。したがって、挿入操作の半分の時間は O(1) です。残りの半分のうち、半分は2 番目のレベルに属します。等々。挿入時に実際に log(n) 操作を行うのは、挿入する項目が既存のルート項目よりも小さい場合のみです。したがって、観測された実行時の動作が挿入が O(1) である可能性は十分にあります。実際、ソートされた配列を最小ヒープに挿入すると、これが動作します。つまり、値 1、2、3、4、5、6、7、8、9、10 をこの順序で挿入するとします。
最小ヒープから最小のアイテムを削除するときは、ヒープから最後のアイテムを取り出し、上からふるいにかけます。「半分の時間」ルールが再び機能しますが、今回は不利になります。ヒープから最後に取得したアイテムは、おそらく最下層に属しています。したがって、ログをふるいにかける必要があり、これには log(n) 操作が必要です。すべての log(n) 操作に必要な時間の半分です。残りの半分は、そのうちの 1 つを除いてすべて実行する必要があります。実際、ふるいにかける必要があるレベルの最小数は、ツリーの深さによって異なります。たとえば、ヒープに 3 つ以上のアイテムがある場合は、最小のアイテムを削除するには、少なくとも 1 回のふるい分け操作が必要になります。これは、次に低いアイテムが常にツリーの 2 番目のレベルにあるためです。
したがって、平均的なケースでは、バイナリ ヒープへの挿入にかかる時間は O(log n) よりはるかに短いことがわかります。O（1）に近い可能性があります。また、バイナリ ヒープからの削除は、O(log n) の最悪のケースに非常に近くなります。
于 2015-03-17T18:53:59.350 に答える