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

[newpuma (還很新)]

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
推 hopward: 他又不是做sorting
→ hopward: O(n)是1.2.4步的時間
不是做sorting求中位數嗎？雖然只有五個數，但再遞迴求中位數的中位數，那邊沒有sor
ting嗎？
※ 編輯: newpuma (114.136.171.105), 12/06/2016 09:41:08
→ hopward: 5個數排列 就算用初等排序 也才5^2=25是一個常數 然後又
→ hopward: 有n/5組 所以那一步還是花n的時間
→ hopward: 遞迴求中位數的中位數那只是把一堆中位數再丟下去遞迴 所
→ hopward: 以時間就是T(n/5)
→ hopward: 而且遞迴也不是排列中位數 而只是要找中位數的中位數 所
→ hopward: 以遞迴下去也只是要找那n/5個數中的第n/2大的數而已
遞迴找出中位數的中位數也是透過分成n/5堆嗎？
可以理解成分堆的時間就佔據O(n)嗎

問題有點白痴 抱歉QQ
※ 編輯: newpuma (114.136.171.105), 12/06/2016 10:00:01
推 hopward: 1.2.4各花n 加起來還是n 所以他就省略了
推 shortid: Sort o(n)是因為每堆只有5個 假設採n log n的sorting 也
→ shortid: 才5log5 是常數 因為有n/5堆 所以總共是nlog5 是O(n)
！！！原來
推 a15151616: 那個O(n)你用第四步驟看 全部的數跟P比大小分堆 至少要
→ a15151616: 比較n次
推 aa06697: 可以google median of median 網路上有很多講解～
※ 編輯: newpuma (114.136.16.228), 12/06/2016 15:30:03