出典：公益社団法人 日本技術士会「技術士第一次試験 過去問題」
計算量のオーダ表記(ビッグO記法)に関する4つの式(5n³+1=O(n³)、nlog₂n=O(n^1.5)、n³3ⁿ=O(4ⁿ)、2^(2ⁿ)=O(10^(n^100)))の正誤を判定する問題。多項式・指数・二重指数の増加率の比較の理解が必要。
アルゴリズムの計算量を表す漸近的記法(オーダ表記)に関する4つの式(ア)〜(エ)について、それぞれの正誤を判定する問題。
① 増え方の速さ: 対数 < 多項式 < 指数 < 2重指数。係数や低い次数は無視できる
② ア正(n³が主)、イ正(log n は √n より遅い)、ウ正(n³·3ⁿ/4ⁿ=n³(3/4)ⁿ→0)、エ誤(2^(2ⁿ)は2重指数で 10^(n¹⁰⁰) より速く増える)
③ 正・正・正・誤(③)
(ア)5n³+1は最高次の項5n³が支配的であり、定数倍や低次の項はオーダ表記では無視できるため、5n³+1=O(n³)は正しい。(イ)nlog₂nとn^1.5を比較すると、n log₂n / n^1.5 = log₂n / n^0.5であり、これはnが大きくなるにつれて0に収束する(対数関数は任意の正のべき乗根よりも増加が遅い)ため、nlog₂n=O(n^1.5)は正しい。(ウ)n³3ⁿと4ⁿを比較すると、n³3ⁿ/4ⁿ = n³(3/4)ⁿであり、(3/4)ⁿは指数的に0に収束し多項式n³の増加を上回って抑え込むため、n³3ⁿ=O(4ⁿ)は正しい。(エ)2^(2ⁿ)は二重指数関数であり、10^(n^100)は(nの100乗を指数とする)単一指数関数である。二重指数関数は単一指数関数よりもはるかに速く増加するため、2^(2ⁿ)=O(10^(n^100))は誤りである。したがってア=正、イ=正、ウ=正、エ=誤の組合せである③が正しい。
オーダ表記では、多項式の最高次の項以外(係数・低次項)は無視できる。関数の増加率の大小関係は、対数関数<多項式関数<指数関数<二重指数関数の順で急激になる、という基本的な階層構造を覚えておくと、この種の比較問題に素早く対応できる。
キーワード: 計算量、オーダ表記、ビッグO記法、情報・論理