[理工] [演算法] 找第k小的數

看板Grad-ProbAsk作者 (方格子)時間15年前 (2011/02/15 18:25), 編輯推噓1(1推 0噓 11→)
留言12則, 5人參與, 最新討論串1/1
用的是prune-and-search的方法 有幾個問題想要問 對n個元素分成 n/5(取上高斯)個集合 對每個集合做sort 對所有集合的中位數收成集合S' 找S'的中位數為p 則可以分成S1, S2, S3 其中S1的數都小於p S2的數都等於p S3的數都大於p 問題1: 在找S'的中位數的時候，要不要將所有的集合以它們的中位數做排序? 問題2: 為什麼在對每個集合做sort時，時間複雜度是n*O(1) 用的是什麼sort演算法呢? 問題3: 最後得到T(n) = T(n/5) + T(3n/4) + O(n) 利用recursion tree可知T(n) = θ(n) 在這一步有需要把recursion tree的做法詳細做出來嗎? 還是只需要寫利用recursion tree可知T(n) = θ(n)就好? --
推
,
老闆都不懂.. ( ′-`)y-～
→
,
這裡禁煙喔XDDDD
-- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.132.121
→
02/15 18:36, , 1F
1. 就套用這個演算法找第k小就可以找到了
02/15 18:36, 1F
→
02/15 18:37, , 2F
2. 我想是因為個數很少, 才5個的關係所以很快...
02/15 18:37, 2F
→
02/15 18:37, , 3F
3. 時間夠的話多寫不會多錯...
02/15 18:37, 3F
→
02/15 18:39, , 4F
2.因為你已經知道有五個，利用爆破的方式可以求出，跟n無關
02/15 18:39, 4F
爆破的方式?
推
02/15 18:39, , 5F
1.不用 2.因為一組5個數,很少 3.隨便畫一下吧
02/15 18:39, 5F
因為他寫Sort each subset of elements需要n*O(1) 可是我不懂，不是有n/5個set要sort為什麼不是 n/5 * O(1) ? ※ 編輯: annheilong 來自: 61.228.132.121 (02/15 22:28)
→
02/15 22:48, , 6F
若你要排序N個數，可以寫兩個迴圈像是seletion sort那樣，但
02/15 22:48, 6F
→
02/15 22:49, , 7F
你已經知道只有五個數，可以把迴圈展開，依complexity來看，
02/15 22:49, 7F
→
02/15 22:49, , 8F
他是O(1)+O(1)+...+O(1)為常數次，跟N沒有關係
02/15 22:49, 8F
→
02/15 23:16, , 9F
就是...眼算法=o(1)
02/15 23:16, 9F
→
02/15 23:18, , 10F
n/5*O(1)是對的 不過既然你是要說成時間複雜度就取O(n)
02/15 23:18, 10F
→
02/15 23:18, , 11F
那個沒影響
02/15 23:18, 11F
謝謝樓上的大大們 ※ 編輯: annheilong 來自: 61.228.132.121 (02/15 23:46)
→
09/11 14:16, , 12F
3. 時間夠的話多寫不 https://daxiv.com
09/11 14:16, 12F
‣ 更多 annheilong 的文章
文章代碼(AID): #1DMbI0AI (Grad-ProbAsk)