資格部

資格・検定の試験情報、対策方法、問題解説など

基礎科目 令和3年度 Ⅰ-2-6

   

 アルゴリズムの計算量は漸近的記法(オーダ表記)により表される場合が多い。漸近的記法に関する次の(ア)〜(エ)の正誤の組合せとして,最も適切なものはどれか。ただし,正の整数全体からなる集合を定義域とし,非負実数全体からなる集合を値域とする関数f,gに対して,f(n)=O(g(n))とは,すべての整数n≧n0に対してf(n)≦c・g(n)であるような正の整数cとn0が存在するときをいう。

  1. 5n3+1=O(n3)
  2. nlog2n=O(n1.5)
  3. n33n=O(4n)
  4. 22n=O(10n100)

解答・解説

解答

 ③

解説

  1. 5n3+1=O(n3) ⭕️
    正しいです。

  2. nlog2n=O(n1.5) ⭕️
    正しいです。

  3. n33n=O(4n) ⭕️
    正しいです。

  4. 22n=O(10n100) ❌
    左辺のべき乗2nは右辺のべき乗100nよりもはるかに大きくなるため,誤りです。

参考情報

過去の出題

 なし

オンラインテキスト
準備中

 

前問 一覧 次問