メモリ管理における最適適合(best-fit)アルゴリズムの特徴

最適適合(best-fit)アルゴリズムは、要求されたサイズ以上の空き領域の中で、サイズが最小の領域を探して割り当てる方式です。「空き領域の大きさをキーとする2分探索木」を構成することで、要求サイズ以上の最小領域を平均 $O(\log n)$ の計算時間で高速に探索できるため、平均処理時間が最も短くなります。 アドレスをキーとする2分探索木では、領域の大きさ順に並んでいないため、要求サイズ以上の最小領域を探すには木全体を走査する必要があり、$O(n)$ の時間がかかります。 大きさが小さい順の片方向連結リストでは、先頭から順に要求サイズ以上の領域を探す線形探索となり、平均 $O(n)$ の時間がかかります。 ビットマップ方式は固定サイズブロックの空き管理に適しており、可変長領域の最適適合を求めるには連続したビット列の探索が必要となり時間がかかります。

要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合(best-fit)アルゴリズムを用いる場合,空き領域を管理するためのデータ構造として,メモリ割当て時の平均処理時間が最も短いものはどれか。

出典令和5年度 春期 応用情報技術者試験 午前 問5
ア
空き領域のアドレスをキーとする2分探索木
イ
空き領域の大きさが小さい順の片方向連結リスト
ウ
空き領域の大きさをキーとする2分探索木
エ
アドレスに対応したビットマップ