基本情報技術者試験「探索アルゴリズム」の問題
衝突がほとんど起きないよう設計されたハッシュ表を用いた探索の、平均的な計算量はどれか。
アO(1)であり要素数にほぼ依存しない
イO(log n)で要素数の対数に比例する
ウO(n)で先頭から順に全件を調べる
エO(n log n)で整列を伴う
正解
ア．O(1)であり要素数にほぼ依存しない
ハッシュ探索はキーをハッシュ関数で計算した位置に直接アクセスする。衝突がほぼ無ければ位置計算と1回の照合で済み、要素数nに依存しない平均O(1)となるため正しい。
?選択肢ごとの解説
ア ○ハッシュ探索はキーをハッシュ関数で計算した位置に直接アクセスする。衝突がほぼ無ければ位置計算と1回の照合で済み、要素数nに依存しない平均O(1)となるため正しい。
イ ×O(log n)は二分探索やバランス木の量であり、範囲を半減する探索の特性で、位置を直接計算するハッシュとは原理が異なる。
ウ ×O(n)は線形探索の量で、先頭から全件を走査する手法の特性であり、直接アクセスするハッシュ探索とは異なる。
エ ×O(n log n)は整列の計算量であり、探索単体の量ではないうえハッシュ探索は整列を必要としない。
✎くわしく
ハッシュ探索は理想的には平均O(1)だが、衝突が多発すると最悪O(n)に劣化する。衝突対策(チェイン法・オープンアドレス法)と負荷率の管理が性能の鍵で、データは整列不要という点も二分探索との違いである。
✓本番での押さえどころ
試験のコツ
『位置を計算で直接=O(1)(ハッシュ)』『半分に絞る=O(log n)(二分)』『全件走査=O(n)(線形)』で覚える。
覚え方
ハッシュは『住所をその場で計算して直行』=探す手間ゼロ=O(1)、と直接アクセスを連想する。
よくある誤り
探索といえば二分探索のO(log n)と即答してしまう誤りが多い。ハッシュは位置を計算で求めるO(1)と区別する。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0137