1

ヒープに関する簡単な概念を理解しようとしています。

Floydアルゴリズムを使用するBuildHeapは、サイズnのヒープを構築するためにTheta（n）を使用することを知っています。この実行時間を取得する方法は、ヒープを下から上に構築することです。このようにして、ヒープの量が多いほど、作業量が少なくなります。

私はこの概念についてエクササイズをしましたが、1つの異なる詳細で、質問は次のとおりでした：

「既知の「FixHeap」がTheta（log（n））ではなくTheta（log（log（n））を使用するとします。新しい「FixHeap」を使用してサイズNの最大ヒープを構築するためのBuildHeapアルゴリズムの実行時間はどのくらいになりますか。 'アルゴリズム（現在Theta（log（log（n）））のみを使用するアルゴリズム） "

新しく指定されたFixHeapの実行時間が、アルゴリズム全体の実行時間にどのように影響するかわかりません。変更内容を理解するのを手伝っていただけませんか。

FixHeapは、親をその左右の子と比較し、親に最大値を設定する既知のアルゴリズムです。リーフの親である頂点のFixHeapは、最大1つの置換を実行し、この頂点の親は2つの置換を実行する可能性があります。

編集：現在のBuildHeapの実行時間は、次の式で計算されます。

（n / 4）* 1 +（n / 2）* 2 +（n / 3）* 3 + ...... + 1 * logn-1

最大で1つの変更を行うn/4の親があり、最大で2つの変更を行うn/2があるという理由だけで...

今は数式の変化がわかりません。

ありがとうございました！

4

1 に答える 1

2

このアルゴリズムにはまだ Θ(n) 時間がかかります。これを見るために、アルゴリズムが O(n) と Ω(n) であることを示すことができます。

O(n) の部分については、このアルゴリズムは、FixHeap がそれぞれ O(log n) 時間かかるバージョンよりも漸近的に遅くなることは明らかにないことに注意してください。その 2 番目のケースでは heapify アルゴリズムに O(n) 時間がかかるため、O(log log n) 時間のケースでも O(n) 時間のバインドを得ることができます。

Ω(n) 部分については、ヒープ化アルゴリズムは、配列の前半の要素ごとに FixHeap プロシージャを 1 回実行することによって機能することに注意してください。n 要素の配列の半分を反復処理するには、少なくとも Ω(n) 時間がかかり、必要な下限が得られます。

お役に立てれば！

于 2013-02-08T17:20:27.900 に答える