[問題] 資結-時間複雜度

[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) 以上皆錯

  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
→ icrts:第2題a應該對，第一題卡在英文囧
→ icrts:應該是a @@
→ icrts:或b 囧 logarithmetic跟log linear 不是很懂