作者NTUmaki (西木野真姬)
看板Grad-ProbAsk
標題[理工] 演算法 closest pair
時間Sat Oct 3 14:23:13 2020
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1601706195.A.5BE.html
1F：推 FRAXIS: merge 應該是 k 從頭掃到尾 10/04 21:25
K沒有divide的話會n^2哦！
2F：→ NTUmaki: 我這幾天研究完了～ 實際上不能從頭掃到尾 這樣一定是n^2 10/04 21:44
※ 編輯: NTUmaki (27.52.131.223 臺灣), 10/04/2020 21:44:26
3F：→ NTUmaki: 林立宇這邊講的沒有很清楚 詳細可以參考網路上其他資源， 10/04 21:46
4F：→ NTUmaki: 正確做法是維護兩個陣列，一個是對x sort (x座標相同則再 10/04 21:46
5F：→ NTUmaki: 對y 排，否則會無法分成n/2） 一個是對y sort 然後兩個陣 10/04 21:46
6F：→ NTUmaki: 列都要切半 10/04 21:46
7F：→ NTUmaki: 如果按照林立宇的版本，一直都是對你presort 的 K 從頭掃 10/04 21:47
8F：→ NTUmaki: 到尾的話 複雜度會是n^2 不信的可以寫程式跑跑看就知道了 10/04 21:47
9F：推 joywilliamjo: 離題，想請問有資工考科的賴群嗎？ 10/05 09:39
10F：推 FRAXIS: 對 x sort 不是必須的，只要找到 median 就可以切了 10/06 21:13
11F：→ FRAXIS: 兩個陣列都要切半是沒錯 這樣才能減少搜尋範圍 10/06 21:14
12F：推 misaka0120: ADA崩潰中 10/07 19:11