次のＣ言語のプログラムで、n ≧ 2として関数 f を呼び出したとき、f の内部で f 自身が呼び出される回数を n のオーダで表したものを選べ。
int f(int n)
{
if ( n < 2 )
return 1 ;
else
return f(n-1) + f(n-2) ;
}
① Ο(n) ②Ｏ(nlogn) ③ Ο(n2)
④ Ｏ((1+√5)/2)n) ⑤ Ο(n!)
④
f(2) = f(1) + f(0) = 1 + 1 = 2回
f(3) = f(2) + f(1) = (f(1) + f(0)) + 1 = 2 + 1 = 3回
f(4) = f(3) + f(2) = 3 + 2 = 5回
f(5) = f(4) + f(3) = 5 + 3 = 8回
f(6) = f(5) + f(4) = 8 + 5 = 13回
f(7) = 21回
f(8) = 34回
f(9) = 55回
f(10) = 89回
n に対してこのように値が変化するのに近いものは、④である。
n = 2 :2.618033989
n = 3 :4.236067977
n = 4 :6.854101966
n = 5 :11.09016994
n = 6 :17.94427191
n = 7 :29.03444185
n = 8 :46.97871376
n = 9 :76.01315562
n =10 :122.9918694
| Ⅳ－３ | 目次 | Ⅳ－５ |