如果 x1 ≤ x2 且 y1 ≤ y2,则假设坐标 (x1,y1) 处的一个点支配另一个点 (x2,y2);
我有一组点 (x1,y1) , ....(xn,yn) 并且我想找出支配对的总数。我可以通过比较所有点来使用蛮力来做到这一点,但这需要时间 O(n2)。相反,我想使用分而治之的方法及时解决这个问题 O(n log n)。
现在,我有以下算法:
绘制一条垂直线,将点集分为 Pleft 和 Pright 两个相等的子集。作为基本情况,如果只剩下两个点,我可以直接比较它们。
递归计算Pleft和Pright
中的支配对数量一些征服步骤?
问题是我在这里看不到“征服”步骤应该是什么。我想计算从 Pleft 到 Pright 有多少个支配对,但如果不比较两者的所有点,我不知道该怎么做部分,这将花费时间 O(n2)。
谁能给我一些关于如何进行征服步骤的提示?
所以 y 坐标的两半是:{1,3,4,5,5} 和 {5,8,9,10,12}
我画了分割线。
最佳答案
假设您分别按 y 坐标升序对两半中的点进行排序。现在,查看两半中的最低 y 值点。如果左侧最低点的 y 值低于右侧最低点,则该点受右侧所有点支配。否则,右边的底点不会支配左边的任何东西。
无论哪种情况,您都可以从两半中的一个中删除一个点,然后对剩余的排序列表重复该过程。这确实每个点 O(1) 工作,所以如果有 n 个总点,这 O(n) 工作(排序后)来计算两半的主导对的数量。如果您以前见过它,这类似于计算数组中反转的算法)。
考虑到对点进行排序所需的时间 (O(n log n)),此征服步骤需要 O(n log n) 时间,从而给出递归
T(n) = 2T(n / 2) + O(n log n)
根据 Master Theorem 求解为 O(n log2 n) .
但是,您可以加快速度。假设在开始分而治之步骤之前,您按 y 坐标对点进行预排序,完成一次 O(n log n) 工作。使用类似于最近点对问题的技巧,您可以在 O(n) 时间内对每个大小为 n 的子问题(请参阅 the discussion at this bottom of this page 了解详细信息)排序。这将重复更改为
T(n) = 2T(n / 2) + O(n)
根据需要求解为 O(n log n)。
希望这对您有所帮助!
关于algorithm - 用于计算控制点的分而治之算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19510564/