1. PTT
  2. Prob_Solve

[問題] Sorting in O(n)...

作者: shaopin (Brian)   2014-10-27 13:35:39
今天看CLRS 看到一題 Problem
假設在一個圓裡面 均勻分佈著 n 個點
目標是要依照每個點對(0,0)的距離排序
每個點都是(x,y) x^2+y^2 <=1
題目要求O(n) 原文中有 hint 只是還沒時間想出來
請問這和有沒有均勻分佈有什麼關係?
作者: freef1y3 ( )   2014-10-27 16:03:00
若沒有均勻分布，所有點都在 x 軸上，就變成排序 N 個數這樣就不可能 O(N) 了，所以可能跟均勻分布有關吧只是均勻分布有沒有更精確的定義呢
作者: flere (人間失格)   2014-10-27 19:41:00
聽過類似的, 我想應該是bucket sort吧
作者: FRAXIS (喔喔)   2014-10-27 21:59:00
你要了解uniform distribution in disk的概念..http://mathworld.wolfram.com/DiskPointPicking.html然後就可以設計bucket了..
繼續閱讀
[問題] selection problemjb679123[問題] 不重疊的圓求最大面積jjwang[問題] 時間複雜度qwerty147852Re: [問題] 給定n個排好序的整數陣列 找中位數FRAXISRe: [問題] 給定n個排好序的整數陣列 找中位數DJWSRe: [問題] 給定n個排好序的整數陣列 找中位數chzRe: [問題] 給定n個排好序的整數陣列 找中位數dreamoonRe: [問題] 給定n個排好序的整數陣列 找中位數DJWSRe: [問題] 給定n個排好序的整數陣列 找中位數FRAXISRe: [問題] 給定n個排好序的整數陣列 找中位數DJWS

Links booklink

Contact Us: admin [ a t ] ucptt.com