技術士第一次試験｜無料Web版
技術士 基礎科目 令和3年度 Ⅰ－２－６｜問題と解説
問題 Ⅰ－２－６
アルゴリズムの計算量は漸近的記法（オーダ表記）により表される場合が多い。漸近的記法に関する次の（ア）〜（エ）の正誤の組合せとして、最も適切なものはどれか。
1 ア：正 イ：誤 ウ：誤 エ：誤
2 ア：正 イ：正 ウ：誤 エ：正
3 ア：正 イ：正 ウ：正 エ：誤
4 ア：正 イ：誤 ウ：正 エ：誤
5 ア：誤 イ：誤 ウ：誤 エ：正
問題図表
正解と解説
正解：3
解説f(n)＝O(g(n))は、十分大きいnで比f(n)/g(n)が定数以下に抑えられることを意味する。各式の比を比べる。
1．多項式と対数を比較する
アはn≧1で 5n3＋1≦6n3だから正しい。イの比は log2n√n→0。対数の増大は正のべきより遅いため、イも正しい。
2．指数関数の比を取る
ウは n33n4n＝n3(3/4)n。指数的な減衰がn3の増大に勝ち、比は0に近づくため正しい。
3．二重指数は対数で比較する
エでは f＝22n、g＝10n100。比の自然対数は ln(f/g)＝(ln 2)2n−(ln 10)n100となる。2nはn100より速く増えるので、この差は＋∞に向かう。比が有界でないため、エは誤り。
ア：正、イ：正、ウ：正、エ：誤。二重指数の入れ子を通常の2n乗と読み替えない。
関連知識 オーダ表記では定数倍と低次項を無視し，最高次の増加率だけを見る。 an は多項式 nk より速く増大する。
問題・正答の出典：公益社団法人 日本技術士会（公式の過去問題・公式正答）
掲載している解説は日本技術士会の公式解説ではありません。