探索アルゴリズムの計算量
応用情報技術者 用語
探索アルゴリズムの計算量は、データの件数nに対して探索にかかる比較回数や時間の増え方です。線形探索は平均O(n)、2分探索木は平均O(log n)、衝突のないハッシュ表はデータ件数に関係なく一定です。
取り違えやすい用語
- アドレスをキーとする2分探索木と大きさをキーとする2分探索木（最適適合で速く探せるのは大きさをキーとする方）
- 線形探索で見つかる場合と見つからない場合の比較回数（見つかる場合は平均(n＋1)/2回、見つからない場合はn回）
- ハッシュ表と線形探索の探索時間（ハッシュ表は件数に関係なく一定、線形探索は件数に比例）
試験での出方
- 最適適合で空き領域を探すとき、平均処理時間が最も短いデータ構造を選ぶ（令和5年度 春期 問5）
- 探索するデータが表に存在しない確率を含めて、線形探索の平均比較回数の式を求める（令和5年度 春期 問6）
- 衝突のないハッシュ表の探索時間とデータ件数の関係を示すグラフを選ぶ（令和5年度 春期 問19）
出題された回
全年度から出題。10問で実力を判定します。登録不要。
解説と用語ページは生成 AI が書き、別の生成 AI が確かめています。作り方