看板 [ Prob_Solve ]
討論串[問題] median of median的時間複雜度
共 2 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] median of median的時間複雜度
推噓1(1推 0噓 0→)留言1則，0人參與, 最新作者mqazz1 (無法顯示)時間14年前 (2010/05/01 14:11), 編輯資訊
1
0
0
內容預覽:
我看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. ＝
(還有252個字)
#2
Re: [問題] median of median的時間複雜度
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者GiPaPa (揪濘)時間14年前 (2010/05/03 14:11), 編輯資訊
0
0
0
內容預覽:
整理: -c( n/10 - 7) + an ≦ 0. an ≦ c( (n-70)/10 ). 再乘過去就是下式了因為n大於等於140(詳見遞迴式). 故n/(n-70) ≦2. 故c ≧ 10a(n/(n-70))可寫成. c ≧ 10a(2) =20a. 所以應該是20a 而不是20. ---
(還有241個字)
首頁
上一頁
1
下一頁
尾頁