[理工] [資結]recursive tree, master method
算洪逸老師資結裡的題目遇到問題，晚上想了半天想不出來
題目：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
推
08/10 01:14, , 1F
08/10 01:14, 1F
→
08/10 01:15, , 2F
08/10 01:15, 2F
→
08/10 01:16, , 3F
08/10 01:16, 3F
→
08/10 02:10, , 4F
08/10 02:10, 4F