作者shaopin (problem maker)
看板Prob_Solve
標題[問題] Sorting in O(n)...
時間Mon Oct 27 13:35:39 2014
今天看CLRS 看到一題 Problem
假設在一個圓裡面 均勻分佈著 n 個點
目標是要依照每個點對(0,0)的距離排序
每個點都是(x,y) x^2+y^2 <=1
題目要求O(n) 原文中有 hint 只是還沒時間想出來
請問這和有沒有均勻分佈有什麼關係?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 99.57.137.146
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1414388141.A.2D0.html
→ freef1y3: 若沒有均勻分布，所有點都在 x 軸上，就變成排序 N 個數 10/27 16:03
→ freef1y3: 這樣就不可能 O(N) 了，所以可能跟均勻分布有關吧 10/27 16:03
→ freef1y3: 只是均勻分布有沒有更精確的定義呢 10/27 16:07
推 flere: 聽過類似的, 我想應該是bucket sort吧 10/27 19:41
推 FRAXIS: 你要了解uniform distribution in disk的概念.. 10/27 21:59
→ FRAXIS: 然後就可以設計bucket了.. 10/27 22:00