1

给定 n 对点，我们怎样才能得到能够快速形成正斜率直线的点对数？

然后有 n 行，其中第 i 行包含两个整数 xi 和 yi，指定第 i 个点的 x 和 y 坐标。没有两个点具有相同的 x 坐标，也没有两个点具有相同的 y 坐标。

我的想法是先对 x 进行排序，然后将每个点与它下面的另一个点进行比较。但它仍然是 O(n^2)

4

2 回答 2

4

选择一个点（随机是最简单的并且具有良好的预期运行时间，尽管您可以在线性时间内确定性地找到一个中点），将轴分成四个象限：

  x        |
           |   x   x
     x     |  x
-----------x-----------
  x        |
   x       |      x
           | x

I用, II, III,表示从左上角逆时针方向的象限IV：

II  | I
----|----
III | IV

我们将忽略位于轴上的点（理论概率为 0 的边缘情况，并且在实践中很容易处理）。

请注意，象限中的所有点III与所有点形成一条正斜线I，类似地，没有任何点将II与点形成 ps 线IV，因此我们递归调用：

NumPSLines(G) = |I|*|III| +
                NumPSLines(I U II) +
                NumPSLines(II U III) +
                NumPSLines(III U IV)

whereU表示联合。

假设（留给读者的证明）预期值E(|I|) = ... E(|IV|) = |G|/4 = n/4 和象限的划分是线性的，那么我们得到预期的运行时间：

T(n) = O(n) + 3T(n/2)
     = O(n) + ... + 3^k * t(n/2^k) // where k = log2(n)
     = O( log2(n) * 3^log2(n) )
     = O(n^(log2(3)) * logn)
     ~ O(n^1.6 * logn)

不确定这个界限是否紧密；没有考虑太多。

这个解决方案可以进行超级优化，尽管它只是一个开始。

于 2012-04-28T15:16:21.647 回答
3

按 x 降序排序，然后计算 y 中的反转次数。这两个步骤都是 O(n log n)。

解释：斜率为正的（无序）对的数量是对的数量{(xi, yi), (xj, yj)}，使得 xi > xj 和 yi > yj。当我们按 x 降序排序时，我们使得 xi > xj 当且仅当 i < j 时。ys 中反转的定义是一对 i < j 使得 yi > yj。

快速计算反转次数。

于 2012-04-28T15:29:32.447 回答