algorithm - ヒープの償却分析

Question

このトピックにたどり着いたとき。

5-1 ページの下部にあるこの本の中で、 Binomial Queues、Fibonacci Heap、およびSkew Heapの挿入操作の償却コストは O(1)であり、削除操作の償却コストは O(log n)であると読みました。次に著者は、ペアリング ヒープの挿入操作の償却コストは O(1) であり、削除操作の償却コストは O(log n) であると書いています。

この宿題では、ヒープのタイプを定義せずに、このリンクの 3 番目 (3) の割り当てと解決策 が挿入用に O(log n) を、削除用に O(1) を書きました。

この宿題で別の著者は、二項ヒープには挿入操作の O(log n) と削除操作の償却コスト O(1) があると述べています。

問題は、どちらが正しいかです。私はかなり混乱しています。

Answer 1

ヒープには非負の数の要素があるため、空のヒープから開始すると、常に #inserts ≥ #deletes となります。したがって、償却された時間境界では、O(1) 挿入/O(log n) 削除は、挿入が対応する削除 (存在する場合) を前払いするようにアカウンティングを変更することにより、O(1) 挿入/O(log n) 削除を意味します。そこに矛盾はありません。