使用分而治之找到最接近的对
Finding the closest pair using Divide and Conquer
我目前被分配创建一个 c++ 程序来查找 (x,y) 坐标系中最近的一对点。但是，我在尝试理解一件事时遇到了很多麻烦。
我读到的关于最近对问题的每个 tutorial/guide 都告诉我根据 Y 坐标对点集进行排序，但我不明白这是什么意思？有人可以向我解释为什么我们按 Y 坐标对其进行排序以及它的用途是什么？我知道我们按 X 对点进行排序以获得 L 和 X*，但我不明白为什么我们也必须按 Y 坐标对点进行排序。
你没有，但是你的 运行 时间并没有改善 O(n2)。重点是尽可能少地计算——通过检查尽可能少的点，忽略那些你知道不会成为答案一部分的点。通过对 Y 进行排序来做到这一点。
这是我刚刚用谷歌搜索的一个很好的解释：http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html
我目前被分配创建一个 c++ 程序来查找 (x,y) 坐标系中最近的一对点。但是，我在尝试理解一件事时遇到了很多麻烦。
我读到的关于最近对问题的每个 tutorial/guide 都告诉我根据 Y 坐标对点集进行排序，但我不明白这是什么意思？有人可以向我解释为什么我们按 Y 坐标对其进行排序以及它的用途是什么？我知道我们按 X 对点进行排序以获得 L 和 X*，但我不明白为什么我们也必须按 Y 坐标对点进行排序。
你没有，但是你的 运行 时间并没有改善 O(n2)。重点是尽可能少地计算——通过检查尽可能少的点，忽略那些你知道不会成为答案一部分的点。通过对 Y 进行排序来做到这一点。
这是我刚刚用谷歌搜索的一个很好的解释：http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html