ハッシュ法の平均探索計算量
衝突が少ない理想的なハッシュ表における、データ探索の平均計算量(オーダ)はどれか。
解説を見る
ハッシュ法はキーからハッシュ関数で格納位置を直接計算するため、衝突が少なければ要素数に依存せず平均 O(1) で探索できる。
誤答の解説
BO(log n) は2分探索や平衡木の計算量。
CO(n) は線形探索の計算量(衝突が極端に多いと近づく)。
DO(n^2) は二重ループの計算量。
ヒント
・位置を「計算」で一発で求められる。
・位置を「計算」で一発で求められる。