平成24年秋期試験問題 午前問3
問3解説へ
探索方法とその実行時間のオーダーの適切な組合せはどれか。ここで,探索するデータの数をnとし,ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。また,実行時間のオーダーがn2であるとは,n個のデータを処理する時間がcn2(cは定数)で抑えられることをいう。
広告
解説
オーダー記法は、アルゴリズムの計算量が実行時に処理するデータ量によってどのように増加するかやアルゴリズムの実行時間の長さを示します。時間計算量を表すオーダー記法によってアルゴリズムの複雑さがわかり、アルゴリズムの理論的比較ができます。
探索方法とオーダーの組合せは次の表のようになっています。したがって正しいのは「ア」になります。
探索方法とオーダーの組合せは次の表のようになっています。したがって正しいのは「ア」になります。
広告