[問題] median of median的時間複雜度

[mqazz1 (無法顯示)]

我看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
推 FRAXIS:a應該是某一個常數..然後帶進去吧