推 john35452:我看妳題目旁邊畫的recursion tree，c只是常數，所以所 08/10 01:14
→ john35452:有的地方都是c，沒有倍數。把c當作1的話，這題變成1+2+4 08/10 01:15
→ john35452:+8+...+2^k-1=2^k-1=O(n-1)=O(n) 08/10 01:16
→ yulinya: 終於搞懂了~非常謝謝你!!!:^) 08/10 02:10
算洪逸老師資結裡的題目遇到問題，晚上想了半天想不出來
題目：http://ppt.cc/m~3T
我卡住的點是不知道為什麼recursive tree解出來的答案和Master method不同，
老師給的正確答案是Master method的解，但我想不出來recursive tree的求法解錯哪裡?
我用recursive tree解第一層的時間複雜度是常數倍的時間，
total level cost 是 c(每一層的cost)*log n(樹的高度)，時間複雜度為O(log n)，
所以最終算出的時間複雜度為O(log n)，
算出來和Master method 的O(n)不同，不知道是我哪裡算錯了？
啊啊啊～不知道有沒有表達清楚，希望有人可以幫忙解惑，謝謝！:^)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 58.115.12.197
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1407599809.A.599.html
※ 編輯: yulinya (58.115.12.197), 08/10/2014 00:09:08