[理工] [DS]遞迴樹

看板Grad-ProbAsk作者 (大大督)時間14年前 (2012/02/25 21:15), 編輯推噓1(1推 0噓 11→)
留言12則, 6人參與, 最新討論串1/1
T(n) = T(n/3) + T(2n/3) + n 求此遞迴tree的高度 該如何求呢? 謝謝~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 125.232.86.19
→
02/25 21:19, , 1F
精確的話 log n 底數3/2 隨便的話就O(logn)
02/25 21:19, 1F
→
02/25 21:20, , 2F
ya 猜對
02/25 21:20, 2F
→
02/25 21:25, , 3F
Θ(nlog(n))
02/25 21:25, 3F
→
02/25 21:29, , 4F
忘了打，上面那個是 T(n) 的複雜度
02/25 21:29, 4F
→
02/25 21:30, , 5F
若考慮 T(n) = T(αn) + T((1-α)n) + n
02/25 21:30, 5F
→
02/25 21:31, , 6F
且令 (t,r) = (1/α,1/(1-α)) , 則 tree high 的
02/25 21:31, 6F
→
02/25 21:32, , 7F
upper bound 是 max( lg_t n, lg_r n )
02/25 21:32, 7F
→
02/25 21:33, , 8F
lower bound 是 min( lg_t n, lg_r n)
02/25 21:33, 8F
→
02/26 15:28, , 9F
upper bound是O(n log n) lower bound是Ω(n log n)
02/26 15:28, 9F
→
02/26 15:30, , 10F
夾擠法 所以 T(n)=Θ(nlogn)沒錯
02/26 15:30, 10F
推
02/29 10:37, , 11F
1/3 + 2/3 = 3/3 case 2 of 老大定理 所以 nlogn
02/29 10:37, 11F
→
09/11 14:59, , 12F
精確的話 log n https://daxiv.com
09/11 14:59, 12F
‣ 更多 DADADODO 的文章
文章代碼(AID): #1FIDxT55 (Grad-ProbAsk)