[理工] 演算 selection problem之時間複雜度

看板Grad-ProbAsk作者 (還很新)時間9年前 (2016/12/06 09:33), 9年前編輯推噓5(5推 0噓 9→)
留言14則, 4人參與, 最新討論串1/1
http://i.imgur.com/cmfwn1S.jpg
因為在解釋裡好像沒特別說是用什麼樣的sorting方式，其他算法大多是用comparison ba se 還有T(n)=T(n/5)+T(3n/4)+O(n)→→→這個O(n)是哪來的QQ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.171.105 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1480988017.A.9F3.html
推
12/06 09:36, , 1F
他又不是做sorting
12/06 09:36, 1F
→
12/06 09:37, , 2F
O(n)是1.2.4步的時間
12/06 09:37, 2F
不是做sorting求中位數嗎？雖然只有五個數，但再遞迴求中位數的中位數，那邊沒有sor ting嗎？ ※ 編輯: newpuma (114.136.171.105), 12/06/2016 09:41:08
→
12/06 09:43, , 3F
5個數排列 就算用初等排序 也才5^2=25是一個常數 然後又
12/06 09:43, 3F
→
12/06 09:44, , 4F
有n/5組 所以那一步還是花n的時間
12/06 09:44, 4F
→
12/06 09:45, , 5F
遞迴求中位數的中位數那只是把一堆中位數再丟下去遞迴 所
12/06 09:45, 5F
→
12/06 09:45, , 6F
以時間就是T(n/5)
12/06 09:45, 6F
→
12/06 09:47, , 7F
而且遞迴也不是排列中位數 而只是要找中位數的中位數 所
12/06 09:47, 7F
→
12/06 09:47, , 8F
以遞迴下去也只是要找那n/5個數中的第n/2大的數而已
12/06 09:47, 8F
遞迴找出中位數的中位數也是透過分成n/5堆嗎？ 可以理解成分堆的時間就佔據O(n)嗎 問題有點白痴 抱歉QQ ※ 編輯: newpuma (114.136.171.105), 12/06/2016 10:00:01
推
12/06 10:22, , 9F
1.2.4各花n 加起來還是n 所以他就省略了
12/06 10:22, 9F
推
12/06 11:04, , 10F
Sort o(n)是因為每堆只有5個 假設採n log n的sorting 也
12/06 11:04, 10F
→
12/06 11:04, , 11F
才5log5 是常數 因為有n/5堆 所以總共是nlog5 是O(n)
12/06 11:04, 11F
！！！原來
推
12/06 11:13, , 12F
那個O(n)你用第四步驟看 全部的數跟P比大小分堆 至少要
12/06 11:13, 12F
→
12/06 11:13, , 13F
比較n次
12/06 11:13, 13F
推
12/06 13:46, , 14F
可以google median of median 網路上有很多講解～
12/06 13:46, 14F
※ 編輯: newpuma (114.136.16.228), 12/06/2016 15:30:03
‣ 更多 newpuma 的文章
文章代碼(AID): #1OHXLndp (Grad-ProbAsk)