| 第１種情報処理技術者試験 |
1996年度 ＝ 平成8年度 |
午前 |
問5 |
アルゴリズムの計算量を表す方法の一つに、O 記法（0 -notation）がある。これは、問題のサイズを大きくしていったときの、漸近的計算量を示すものである。
いま、サイズnの問題の計算量を表す関数F(n)がF(n) = 2n＋n2のとき、この関数のO 記法はどれになるか。
| ア O (log2n）
| イ O (n)
| ウ O (n log2n)
|
| エ O (n2)
| オ O (2n)
|
オ
アルゴリズムの計算量を表す方法の一つであるO 記法（0 -notation）は、問題のサイズを大きくしていったときの、漸近的計算量を示すものです。O はorderの略であり、O (n)は、“nのオーダー”あるいは“オーダーn”などと呼ばれます。
nをどんどん大きくしていくと、O (n)に要する計算時間は、nに比例して長くなりますが、O (1)に要する計算時間が変化することはありません。このことからも想像できるでしょうが、一般に、O (f(n))とO (g(n))の操作を連続した場合の計算量は、次のようになります。
O (f(n)) + O (g(n)) = O (max(f(n), g(n)))
すなわち、より大きい方の計算量に支配されるのです。
O (2n)＞O (n2)ですから、O (2n)となります。
