※ 引述《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)