※ 引述《FRAXIS (喔喔)》之銘言：
: 推 kill2400:我又看錯 原PO第一題第一拆花n^0.5 06/16 12:38
: → kill2400:課本題目是T(n)=T(n/3)+T(2n/3)+n ===>O(nlogn) 06/16 12:39
: 推 kill2400:可是我用遞迴樹展開第一階成本 n^0.5 第2階成本 06/16 13:01
: → kill2400:((1+2^0.5)/3^0.5)*n^0.5 依此類推 06/16 13:03
: → kill2400:每一階成本差(1+2^0.5)/3^0.5 06/16 13:04
: → kill2400:但這棵樹一定會停 但是我將式子都相加起來然後 06/16 13:05
: → kill2400:樹的成本一定<無限 06/16 13:06
: 噓 kill2400:公比大於1 = = 不能求 06/16 13:18
實際上也不是不能求，公比雖然大於一，但是因為樹高是有限的，
最長就是一直切2/3的那一條路，高度是log_{2/3} n，
最短的就是一直切1/3的那一條路，高度是log_3 n。
可以用等比級數的公式去算總和，令r = (1+2^0.5)/3^0.5
上限就是 n^(0.5) * (r^(log_{2/3} n) - 1)/(r-1)
不過這種題目用公式解可能比較快.. Akra–Bazzi method
解出來應該是Θ(n)..
還是說有什麼其他巧妙的解法？
這題目是從哪裡來的阿..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50
※ 編輯: FRAXIS 來自: 140.119.162.50 (06/16 21:16)