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

看板Grad-ProbAsk作者 (喔喔)時間15年前 (2010/06/15 21:38), 編輯推噓5(6推 1噓 11→)
留言18則, 2人參與, 最新討論串2/3 (看更多)
: 推 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
推
06/15 23:13, , 1F
恩 我覺得也是O(logn) 每次拆都只花O(1) 樹展開
06/15 23:13, 1F
→
06/15 23:14, , 2F
高度O(logn)
06/15 23:14, 2F
→
06/15 23:40, , 3F
但是T(n)又等於2T(n/2) + O(1)，如果用Master Theorem來解
06/15 23:40, 3F
→
06/15 23:41, , 4F
答案應該是O(n) 是我代錯了嗎？ 還是Master Theorem錯了？
06/15 23:41, 4F
推
06/16 01:05, , 5F
看錯 應該是O(n)才對= =
06/16 01:05, 5F
→
06/16 01:06, , 6F
F說對
06/16 01:06, 6F
推
06/16 01:15, , 7F
對了 如果用遞迴樹解 解的出O(n)嗎?剛剛突然想到
06/16 01:15, 7F
推
06/16 01:20, , 8F
恩 可以
06/16 01:20, 8F
→
06/16 10:00, , 9F
其實我只是要說明.. 原Po的第一題至少也是O(n)..
06/16 10:00, 9F
→
06/16 10:01, , 10F
不會是n^(1/2)log(n)這麼小的東西..
06/16 10:01, 10F
推
06/16 12:38, , 11F
我又看錯 原PO第一題第一拆花n^0.5
06/16 12:38, 11F
→
06/16 12:39, , 12F
課本題目是T(n)=T(n/3)+T(2n/3)+n ===>O(nlogn)
06/16 12:39, 12F
推
06/16 13:01, , 13F
可是我用遞迴樹展開第一階成本 n^0.5 第2階成本
06/16 13:01, 13F
→
06/16 13:03, , 14F
((1+2^0.5)/3^0.5)*n^0.5 依此類推
06/16 13:03, 14F
→
06/16 13:04, , 15F
每一階成本差(1+2^0.5)/3^0.5
06/16 13:04, 15F
→
06/16 13:05, , 16F
但這棵樹一定會停 但是我將式子都相加起來然後
06/16 13:05, 16F
→
06/16 13:06, , 17F
樹的成本一定<無限
06/16 13:06, 17F
噓
06/16 13:18, , 18F
公比大於1 = = 不能求
06/16 13:18, 18F
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1C5u9bwK (Grad-ProbAsk)
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1C5u9bwK (Grad-ProbAsk)