[理工] DS 時間複雜度

[j897495 (咪咪)]

(1)Time for merge-sort can be modeled as the recursion T(n)=2T(n/2)+cn
that has solution theta(nlogn).And balance recursion achieves the best result.
Thus the lower bound to sorting problem is Omega(nlogn).

這個敘述錯在哪呢?
Merge-sort的best/average/worst case 都是O(nlogn)沒錯
所以是因為是theta的關係嗎?

(2)

long f (long n){
  if (n<1) return 0;
  if (n<3) return 1;
  return f(n-1)+f(n-2);
 }

The number of recursive calls grows exponentially with n
這句話的意思是 O(2^n)對嗎?

這和費氏數列的時間複雜度應該是一樣的

(3)
6(n^3)/(logn+1)的時間複雜度為什麼是n^3次呢?

logn跟n^3比太小可以忽略嗎??

希望有人能給個指點謝謝!!

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.236.228.251
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1419269247.A.FB0.html
推 FRAXIS: (1) 是錯在這跟 lower bound一點關係都沒有..
→ FRAXIS: (2) 他是說時間複雜度是c^n, c是一個常數未必是2..
→ FRAXIS: (3) 應該是O(n^3) 但是不會是Θ(n^3)
→ j897495: 請問什麼是lower bound@@
→ j897495: 不是下界的意思嗎
推 FRAXIS: 他的敘述每一句 你分開來看都是對的
→ FRAXIS: 但是前兩句不會 imply 第三句
→ j897495: 懂了謝謝你！
推 galapous: 第二題是false？
→ j897495: 是true 只是不太懂表示的意思
推 galapous: 喔喔，3q