技術士 過去問
令和3年度（2021年）
問12 (基礎科目「情報・論理に関するもの」 問12)

正解は３です。

基本的には多項式は乗数を一番大きいものを残して係数を消す、

対数関数や指数関数はそのまま残す、というのがオーダーの考え方になります。

ア：正しい

上記の考え方にのっとり、＋１と５を消してn³を残したものです。

イ：正しい

基本的にはnlog₂nのオーダーはＯ（nlog₂n)です。

ただし、O(n)＜O(nlogn)＜O(n²)となることからO(n^1.5)に近似できると考えます。

ウ：正しい

基本的にはｎが十分大きいとき、n³3ⁿにおいてn³は計算量に影響しないため、O(3ⁿ)となります。なぜ４にしたのかはわかりませんがO(3ⁿ)とO(4ⁿ)は計算量としては等価とみなせます。

エ：誤り

aⁿとn^aは計算量としては明確に異なることからこれは成立しません。

オーダーに関する問題です。

べき乗が一番大きいもののべき乗がオーダーです。

ア：正

5n³＋1のオーダーはO(n³)となります。

イ：正

log₂n<nなので、

n＜nlogn＜n²となることから、O(n^1.5)と近似できます。

ウ：正

ｎが十分大きいとき、n³ ＜＜ 3ⁿであるので、O(3ⁿ)です。

O(3ⁿ)とO(4ⁿ)は、オーダーとしては近似できます。

エ：誤

aⁿとn^aはオーダーが全く違います。

アルゴリズムの計算量に関する出題です。

オーダーの計算は以下のルールに従います。

１．一番大きい項以外は無視（例：4n3+3n2+5n+9 は 4n³ と考える）

２．定数倍の違いは無視 （例： 4n³ は n³ と考える）

３．計算結果をビックオー表記にする

そのあとでただし～という説明が書いてありますが、要はO表記されたものより計算量が少なければ＝と表記しますよということを言っています。

（ア）5n³+1なのでn³が残ります。

（イ）nlog₂nのオーダーはＯ（nlog₂n)です。

ただし、O(n)＜O(nlogn)＜O(n²)になりますので、nlogn²O(n^1.5)よりは低くなります。

（ウ）基本的にはｎが十分大きいとき、n³3ⁿは3ⁿが支配的になります。指数はそれだけ計算量が多いです。なので大体O(3ⁿ)となりますが3ⁿよりは大きいのでO(4ⁿ)と表記しているようです。

（エ）２の2ⁿ乗は4ⁿです。aⁿとn^aは計算量として雲泥の差があり指数のほうがかなり計算量が多いです。