1

フィボナッチ ヒープがグローバル ノード カウンターを保持していると読みましたが、その理由がわかりません。カウンターを持っていたが、まったく使用していない実装も見つけました。

4

1 に答える 1

1

「ヒープに要素がいくつあるか」という形式のクエリを作成することです。O(1) に時間がかかります。この情報をキャッシュしないと、含まれるノードの数をカウントするために各ツリーをトラバースする必要があるため、このクエリには O(n) の時間がかかります。これは、一部のリンク リストの実装がノード数を追跡するカウンターを維持する理由と似ています。

お役に立てれば！

于 2013-11-23T23:28:21.880 に答える