内部データ構造としてバイナリ ヒープを使用するプライオリティ キューを研究しています。ブロック サイズ M の外部メモリ モデルを考慮すると、スライドでは、deleteMin にはほぼ2log(n/M)ブロック アクセスが必要であると主張しています。
どうしてこれなの？ボトムアップ ヒューリスティック (Wegener 93) を記述した元の論文にも、スライドにも説明が見つかりませんでした。
最初のブロックには、ルートとヒープの最初の log(M) レベルが含まれます。その後、ノードごとに、レベルごとに 1 つのブロックを読み取る必要があります。これには、2 つの連続する子ノードが含まれます。ノードの両方の子を取得するために 2 つのブロックを読み取る必要があるのは、ごくまれなケースです (したがって「概算」)。最初のログ (M) レベルは 1 回のブロック アクセスで読み取られるため、最低(log n - log M) = log n/Mレベルのブロックをロードするだけで済みます。
はどこ2から来たのですか？キャッシュの削除時にブロックをディスクに書き戻す必要がありますが、それは通常、負荷で説明されていませんか?
質問を十分に説明できたことを願っています。どうもありがとう！