作者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/cn.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