分野別過去問題テクノロジ系　アルゴリズム No.30

アルゴリズム(全75問中30問目)

探索方法とその実行時間のオーダの適切な組合せはどれか。ここで，探索するデータの数をnとし，ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また，実行時間のオーダがn²であるとは，n個のデータを処理する時間がcn²(cは定数)で抑えられることをいう。

出典：平成24年秋期　問 3

正解　ア問題へ

分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：アルゴリズム

解説

オーダ記法は、アルゴリズムの計算量が実行時に処理するデータ量によってどのように増加するかやアルゴリズムの実行時間の長さを示します。時間計算量を表すオーダ記法によってアルゴリズムの複雑さがわかり、アルゴリズムの理論的比較ができます。

探索方法とオーダの組合せは次の表のようになっています。

したがって正しいのは「ア」になります。