複雑さが 3*N になるような C++ の make_heap のアルゴリズムは何ですか? 要素を挿入してヒープを作成する唯一の方法は、O(N Log N) の複雑さです。どうもありがとう！
6188 次
1 に答える
22
ヒープを配列として表します。番目の要素の下にある 2 つの要素iは、 と の位置2*i+1にあり2*i+2ます。配列にn要素がある場合は、最後から始めて、各要素を取得し、ヒープ内の適切な場所に「落下」させます。これはO(n)実行することです。
なんで？n/2要素の場合、子はありません。n/4高さ 1 のサブツリーがあるからです。n/8高さ 2 のサブツリーがあるからです。高さ 3 のサブツリーがあるからです。以下同様n/16です。したがって、 series を取得します。したがって、「もう一度落ちる必要があるかどうかを確認し、そうであればどの方向に落ちるか?」の比較の総数は になります。それぞれに最大 3 回の比較が必要です (ルートを各子と比較して、それが落ちる必要があるかどうかを確認し、ルートが両方の子よりも大きい場合は、子を相互に比較します)。n/22 + 2*n/23 + 3*n/24 + ... = (n/2)(1 * (1/2 + 1/4 + 1/8 + . ...) + (1/2) * (1/2 + 1/4 + 1/8 + . ...) + (1/4) * (1/2 + 1/4 + 1/8 + . ...) + ...) = (n/2) * (1 * 1 + (1/2) * 1 + (1/4) * 1 + ...) = (n/2) * 2 = nnn
于 2011-02-20T14:42:21.093 に答える