作者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