[問題] median of median的時間複雜度
看板Prob_Solve (計算數學 Problem Solving)作者mqazz1 (無法顯示)時間14年前 (2010/05/01 14:11)推噓1(1推 0噓 0→)留言1則, 1人參與討論串1/2 (看更多)
我看Cormen的書....在導median of median的時間複雜度被困住了
3( 1/2 * n/5 - 2 ) ≧ 3n/10 - 6
T(n) ≦ T(n/5) + T(7n/10 + 6) + O(n)
≦ c(n/5) + c + c(7n/10) + 6c + an
＝ 9cn/10 + 7c + an
＝ cn + (-cn/10 + 7c + an)
which is at most cn if
-cn/10 + 7c + an ≦ 0
-----------------------------------------------------------------
接下來我就算不出來了
c ≧ 10a(n/(n-70)) when n>70
↑這個式子我不知道是怎麼計算出來的..
------------------------------------------------------------------
然後為什麼最後選擇 c ≧ 20 就可以滿足這個不等式呢?
這個在Cormen的191頁..
請高手稍微指點我一下
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.26.91
推
05/01 22:38, , 1F
05/01 22:38, 1F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
