アルゴリズムの本で優先キューに関するこの「絶望的な挑戦」を見ました:
" O(1) 挿入、削除分、および減少キー。なぜそれが不可能なのですか?"
ある種のヒープでそれを実装する唯一の方法であり、ヒープは常に削除に時間がかかるためです（償却された場合でも）？
1054 次
1 に答える
2
n 個の整数を並べ替えるには n * log(n) の時間が必要であるというよく知られた事実を想定し、delete-min が実際に最小値を見つける (たとえば、それを返す可能性がある) と仮定します。
矛盾に向かって、あなたが説明したようなデータ構造があるとします。次に、n 個の整数をソートするために、最初にすべての整数をデータ構造に挿入するため、時間 O(n) がかかります。次に、構造体が空になるまで delete-min を繰り返します。これにより、時間 O(n) でソートされた整数が得られ、矛盾が生じます。したがって、そのデータ構造は存在できません。
于 2013-04-15T01:10:04.203 に答える