配列を使用してヒープを実装し、配列がいっぱいになるたびに、それを 2 倍のサイズの配列にコピーするとします。要素をヒープに挿入する際の償却時間の複雑さ (最悪の場合) はどれくらいですか?
T(n) = n * n(最悪の場合、n 回の操作のシーケンスの総コストの上限) があると思います。1 つの式によると、償却された複雑さはT(n) / n = n^n / n = nです。
しかし、私が得るlog(n)か下げるかは直感的に非常に明確なので、それは非常に間違っていると思います... では、これをどのように計算すればよいでしょうか?
このように表されたヒープに n 個の要素を挿入するとします。考慮する必要があるコストには、次の 2 つの異なるソースがあります。
(1) のコストは、合計 n 回の操作で O(n log n) です。これは、各ヒープ挿入に O(log n) の時間がかかるためです。
(2) のコストについては、配列のサイズを 2 倍にするために行われる作業は、2 倍になった時点での配列のサイズに正比例することに注意してください。これは、配列をサイズ 1 から 2 倍にするために 1 単位の作業を行うこと、サイズ 2 から配列を 2 倍にするために 2 単位の作業を行うこと、サイズ 4 から配列を 2 倍にするために 4 単位の作業を行うことなどを意味します。行われた作業は
1 + 2 + 4 + 8 + 16 + ... + 2 1 + log n ≤ 4n - 1 = O(n)
この計算では、サイズ n になる前に配列を最大で 1 + log n 回だけ 2 倍にするという事実と、1 + 2 + 4 + 8 + ... + 2 k = 2 k+1 - 1という事実を使用しています。 n回の挿入すべてで、配列を2倍にするO（n）作業を行うことを意味します。
全体として、n 回の操作で行われた作業の合計は O(n log n) であるため、操作ごとの償却コストは O(log n) です。