アルゴリズム (全80問中76問目)
No.76
探索方法とその実行時間のオーダーの正しい組合せはどれか。ここで，探索するデータ数をnとし，ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また，実行時間のオーダーがn2であるとは，n個のデータを処理する時間がcn2(cは定数)で抑えられることをいう。
出典：平成16年春期 問11
- [出題歴]
- 基本情報技術者 H17秋期 問11
- 基本情報技術者 H19秋期 問11
- 基本情報技術者 H24秋期 問3
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
ア
解説
オーダー記法は、アルゴリズムの計算量が実行時に処理するデータ量によってどのように増加するかやアルゴリズムの実行時間の長さを示します。時間計算量を表すオーダー記法によってアルゴリズムの複雑さがわかり、アルゴリズムの理論的比較することができます。
探索方法とオーダーの組合せは次の表のようになっています。
したがって正しいのは「ア」になります。
探索方法とオーダーの組合せは次の表のようになっています。