[理工] 演算法 closest pair

[NTUmaki (西木野真姬)]

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
推 FRAXIS: merge 應該是 k 從頭掃到尾
K沒有divide的話會n^2哦！
→ NTUmaki: 我這幾天研究完了～ 實際上不能從頭掃到尾 這樣一定是n^2
※ 編輯: NTUmaki (27.52.131.223 臺灣), 10/04/2020 21:44:26
→ NTUmaki: 林立宇這邊講的沒有很清楚 詳細可以參考網路上其他資源，
→ NTUmaki: 正確做法是維護兩個陣列，一個是對x sort (x座標相同則再
→ NTUmaki: 對y 排，否則會無法分成n/2） 一個是對y sort 然後兩個陣
→ NTUmaki: 列都要切半
→ NTUmaki: 如果按照林立宇的版本，一直都是對你presort 的 K 從頭掃
→ NTUmaki: 到尾的話 複雜度會是n^2 不信的可以寫程式跑跑看就知道了
推 joywilliamjo: 離題，想請問有資工考科的賴群嗎？
推 FRAXIS: 對 x sort 不是必須的，只要找到 median 就可以切了
→ FRAXIS: 兩個陣列都要切半是沒錯 這樣才能減少搜尋範圍
推 misaka0120: ADA崩潰中