[理工] 演算法 closest pair

看板Grad-ProbAsk作者 (西木野真姬)時間3年前 (2020/10/03 14:23), 3年前編輯推噓4(4推 0噓 8→)
留言12則, 4人參與, 3年前最新討論串1/1
https://i.imgur.com/rthlGB3.jpg
學校程式題有出到這題 一直TLE 稍微研究了一下 發現林立宇的code好像有錯 大概以下幾點，如果有人知道我哪邊理解錯 請跟我說 - 1. 林的版本跟楓葉本不一樣 不知道是哪本原文書的？ 2. 他的遞迴要 merge 的時候應該是只要找該遞迴區間（不能K 從頭掃到尾） 3. 但是根據 2 你原陣列跟 K 的區間的點不會一樣 （意思就是 可能你index 6～10 的點 在K跟原陣列不會是同一批點） 4. 所以不能用到那個鴿籠原理（只找7個點） 因為你沒辦法線性時間內找到同時符合|x-m|<=d 然後又可以根據他們y座標排好的順序取點（因為這些 |x-m|<=d 的點在K的位置你不知道） 5. 所以林的版本複雜度應該是n^2 不然程式會錯 ----- Sent from JPTT on my iPhone -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.52.131.223 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1601706195.A.5BE.html
推
10/04 21:25, 3年前 , 1F
merge 應該是 k 從頭掃到尾
10/04 21:25, 1F
K沒有divide的話會n^2哦！
→
10/04 21:44, 3年前 , 2F
我這幾天研究完了～ 實際上不能從頭掃到尾 這樣一定是n^2
10/04 21:44, 2F
※ 編輯: NTUmaki (27.52.131.223 臺灣), 10/04/2020 21:44:26
→
10/04 21:46, 3年前 , 3F
林立宇這邊講的沒有很清楚 詳細可以參考網路上其他資源，
10/04 21:46, 3F
→
10/04 21:46, 3年前 , 4F
正確做法是維護兩個陣列，一個是對x sort (x座標相同則再
10/04 21:46, 4F
→
10/04 21:46, 3年前 , 5F
對y 排，否則會無法分成n/2） 一個是對y sort 然後兩個陣
10/04 21:46, 5F
→
10/04 21:46, 3年前 , 6F
列都要切半
10/04 21:46, 6F
→
10/04 21:47, 3年前 , 7F
如果按照林立宇的版本，一直都是對你presort 的 K 從頭掃
10/04 21:47, 7F
→
10/04 21:47, 3年前 , 8F
到尾的話 複雜度會是n^2 不信的可以寫程式跑跑看就知道了
10/04 21:47, 8F
推
10/05 09:39, 3年前 , 9F
離題，想請問有資工考科的賴群嗎？
10/05 09:39, 9F
推
10/06 21:13, 3年前 , 10F
對 x sort 不是必須的，只要找到 median 就可以切了
10/06 21:13, 10F
→
10/06 21:14, 3年前 , 11F
兩個陣列都要切半是沒錯 這樣才能減少搜尋範圍
10/06 21:14, 11F
推
10/07 19:11, 3年前 , 12F
ADA崩潰中
10/07 19:11, 12F
‣ 更多 NTUmaki 的文章
文章代碼(AID): #1VU1ZJM- (Grad-ProbAsk)