応用情報技術者 2019年 春期 午前2 問05

要求に応じて可変量のメモリを割り当てる最適適合アルゴリズム【午前2 解説】

要点まとめ

• 結論：最適適合（best-fit）アルゴリズムでは空き領域の大きさをキーにした2分探索木が平均処理時間を最短にできる。
• 根拠：最適適合は要求サイズ以上の最小空き領域を探すため、大きさ順に高速検索可能なデータ構造が適している。
• 差がつくポイント：単純なリストやアドレス順管理では探索に時間がかかるが、2分探索木なら$O(\log n)$で最適領域を特定できる点が重要。

正解の理由

よくある誤解

解法ステップ

1. 最適適合アルゴリズムの特徴を理解する（要求サイズ以上の最小空き領域を割り当てる）。
2. 空き領域の管理方法を考える（大きさ順かアドレス順か）。
3. 探索効率を考慮し、要求サイズ以上の最小空き領域を高速に見つけられるデータ構造を選ぶ。
4. 2分探索木は$O(\log n)$で探索可能なため、最適適合に最適。
5. 選択肢を比較し、空き領域の大きさをキーにした2分探索木を選択。

選択肢別の誤答解説

• ア: 空き領域のアドレスをキーにした2分探索木は、アドレス順の管理には有効だが、要求サイズ以上の最小空き領域の探索には不向き。
• イ: 大きさ順の片方向連結リストは探索に$O(n)$かかり、効率が悪い。
• ウ: 空き領域の大きさをキーとする2分探索木は最適適合の探索に最適で正解。
• エ: ビットマップは空き・使用の判別は速いが、最適適合の最小空き領域探索には適さない。

補足コラム

FAQ