Re: [理工] [演算法] 遞迴式問題

[FRAXIS (喔喔)]

: 推 kill2400:請把課本看熟 遞回樹每一階的成本加起來剛好是n           06/15 17:52
: → kill2400:所以是那個答案                                         06/15 17:53
: 推 kill2400:不知道你有沒有"演算法-名校功略秘笈"這一本書            06/15 17:56
: → kill2400:裡面第2-20頁範例5中的第5題跟此題目一模一樣             06/15 17:57
: → kill2400:裡面有詳解                                             06/15 17:58
: → kill2400:nlogn                                                  06/15 17:58
: → kill2400:ㄆㄆ                                                   06/15 17:59
: → kill2400:每一階成本乘上樹高= =                                  06/15 18:00

感謝這位大大的指教，我研究了一下，每一階成本乘上樹高

那我想請問一下

T(n) = T(n/2) + T(n/2) + O(1)

會變成多少？  樹高是O(lg n)應該沒錯吧

所以答案會是O(lg n)?? 或是答案至少裡面有一個lg n項？

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.119.162.50
推 kill2400:恩 我覺得也是O(logn) 每次拆都只花O(1) 樹展開
→ kill2400:高度O(logn)
→ FRAXIS:但是T(n)又等於2T(n/2) + O(1)，如果用Master Theorem來解
→ FRAXIS:答案應該是O(n) 是我代錯了嗎？ 還是Master Theorem錯了？
推 kill2400:看錯 應該是O(n)才對= =
→ kill2400:F說對
推 kill2400:對了 如果用遞迴樹解 解的出O(n)嗎?剛剛突然想到
推 kill2400:恩 可以
→ FRAXIS:其實我只是要說明.. 原Po的第一題至少也是O(n)..
→ FRAXIS:不會是n^(1/2)log(n)這麼小的東西..
推 kill2400:我又看錯  原PO第一題第一拆花n^0.5
→ kill2400:課本題目是T(n)=T(n/3)+T(2n/3)+n ===>O(nlogn)
推 kill2400:可是我用遞迴樹展開第一階成本 n^0.5  第2階成本
→ kill2400:((1+2^0.5)/3^0.5)*n^0.5 依此類推
→ kill2400:每一階成本差(1+2^0.5)/3^0.5
→ kill2400:但這棵樹一定會停 但是我將式子都相加起來然後
→ kill2400:樹的成本一定<無限
噓 kill2400:公比大於1 = = 不能求