0

siftup私はヒープのアルゴリズムを書いていましたが、質問の最後で立ち往生しています。質問の最後の部分は、アルゴリズムは対数の最悪の場合の時間計算量を持つべきであると言っていますO(log(n)。以下にアルゴリズムを記述しました。ここiで、はヒープ内の要素のインデックスであり、vはヒープ配列です。ルートのインデックスは最低ですが、ヒープの最下位の子のインデックスは最大です。配列が1からnになることを検討しています

アルゴリズム

Siftup (v, i) {
While(v[i] > v[i/2] and i != 0) {
    Temp = v[i] // Temp is of the same type as v[i]
    v[i] = v[i/2]
    v[i/2] = temp
    i = i / 2
    }
}

このプロセスには、それぞれが一定の最悪の場合のタイミングを持つ4つの割り当てステートメントが含まれるためwhile loop、アルゴリズムには対数的な最悪の場合の時間計算量が必要です。ヒープ内の要素の数はO(n)どこにあるのかを判断するためのアプローチを示すことができますか？n

PSアルゴリズムのエラーも教えてください。

4

1 に答える 1

1

はい、アルゴリズムは対数的に複雑なようです。

各反復は一定の複雑さを持っているように見えるというあなたの観察に同意します。

その後のステップは、Nの特定の値に対して何回の反復が実行されるかを把握することです。これに対する直接的な答えは提供しませんが、ここで重要なのはi = i / 2です。iこれは逆に見る方が簡単かもしれません。ある特定のNについて、そのNに到達する前に（1から開始して）2倍にする必要がありますか？iより具体的には、Nのサイズと、少なくともNと同じ大きさになるまでに2倍にする必要がある回数との関係は何ですか？

于 2013-02-14T16:00:24.350 に答える