作者sql (peter)
看板Grad-ProbAsk
标题[问题] 资结-时间复杂度
时间Tue Apr 28 18:00:24 2009
1.针对下列时间复杂度(Time Complexity)函数:
Factorial; Constant; Log linear; Cubic; Quadratic; Exponential;
Linear; Logarithmic;
当资料处理量持续增加时，则上述时间复杂度函数大小关系，下列何者为正确?
(a) Constant ﹤Log linear ﹤Linear (b) Logarithmic ﹤Log linear ﹤Quadratic
(c) Quadratic ﹤Cubic ﹤ Factorial (d) Linear ﹤Factorial ﹤ Exponential
(e) 以上皆错
2. [递回程式问题] 有一C 语言之递回程序(recursive procedure)如下:
fib (int n)
{
int x, t;
if (n<=1)
return(n);
x = fib(n-1);
y = fib(n-2);
return(x+y);
}
若第一次呼叫(call) 程序 fib为 fib(6)，即 n 初始值为 6，则请问下列变数(n, x, y)值，在第几次呼叫时为正确。例如第一次呼叫程序fib，则 (n, x, y)=(6, *, *)；第二次呼叫程序fib，则 (n, x, y)=(5, *, *)，其中 * 表示变数尚未有值。
(a) 第9次呼叫，(n, x, y) = (2, 1, 0)
(b) 第12次呼叫，(n, x, y) = (3, 1, 1)
(c) 第14次呼叫，(n, x, y) = (2, *, *)
(d) 第17次呼叫，(n, x, y) = (2, 1, 0)
(e) 第18次呼叫，(n, x, y) = (4, 2, 1)
第2题我选a不知道是否对呢? 请板上高手解答一下^^ 谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 210.69.126.253
1F：→ icrts:第2题a应该对，第一题卡在英文囧 04/30 02:01
2F：→ icrts:应该是a @@ 04/30 02:02
3F：→ icrts:或b 囧 logarithmetic跟log linear 不是很懂 04/30 02:04