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