アルゴリズム (全70問中25問目)

No.25

探索方法とその実行時間のオーダの適切な組合せはどれか。ここで,探索するデータの数をnとし,ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また,実行時間のオーダがn2であるとは,n個のデータを処理する時間がcn2(cは定数)で抑えられることをいう。
  • [この問題の出題歴]
  • 基本情報技術者 H16春期 問11
  • 基本情報技術者 H17秋期 問11
  • 基本情報技術者 H19秋期 問11

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

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

探索方法とオーダの組合せは次の表のようになっています。
03a.gif/image-size:300×62
したがって正しいのは「ア」になります。
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop