Re: [問題] 資結-時間複雜度
※ 引述《sql (peter)》之銘言：
: 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) 以上皆錯
Factorial 例如:n!
Constant 例如:10
Log linear 例如:nlogn
Cubic 例如:n^3
Quadratic 例如:n^2
Exponential 例如:2^n
Linear 例如:n
Logarithmic 例如:logn
所以答案為 b(logn < nlogn < n^2)
c(n^2 < n^3 < n! )
a錯在 log linear < linear (nlogn < n )
d錯在 Factorial < Exponential (n! < 2^n )
: 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: 211.74.246.46
※ 編輯: whisp1222 來自: 211.74.246.46 (04/30 18:51)
推
05/01 01:15, , 1F
05/01 01:15, 1F
→
05/01 01:24, , 2F
05/01 01:24, 2F
→
05/01 10:25, , 3F
05/01 10:25, 3F
討論串 (同標題文章)