PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者GiPaPa (揪濘)時間14年前 (2010/05/03 14:11)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

※ 引述《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( n/10 - 7) + an ≦ 0 an ≦ c( (n-70)/10 ) 再乘過去就是下式了 : c ≧ 10a(n/(n-70)) when n>70 : ↑這個式子我不知道是怎麼計算出來的.. : ------------------------------------------------------------------ : 然後為什麼最後選擇 c ≧ 20 就可以滿足這個不等式呢? 因為n大於等於140(詳見遞迴式) 故n/(n-70) ≦2 故c ≧ 10a(n/(n-70))可寫成 c ≧ 10a(2) =20a 所以應該是20a 而不是20 --- 題外話看你問的這幾個問題感覺你是要考研究所或是要準備學校期中考? 如果是的話不用算的這麼詳細啦算time complexity的題目把遞迴式子寫出來最重要剩下就粗略算給他看就好了 -- 「我是誰」「其實我也是，我只記得自己把皮夾克的袖子部分剪掉了。」「我是誰? 好像確實是保護地球和平的什麼人來著。」 ˍˍ 「說起來的確似曾相識，我好像一直以來都在追逐你。」 ▕攘夷▏ 「可能我們以前就是這樣融合搖滾和RAP來保護世界的吧?」 ▕JｏY▏ ￣￣ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.116.6.166