优化算法从O(n ^ 3)到O(n ^ 2)

Question

我想解决的问题如下:

假设您在二维空间中获得了一组点,并且我们如何获得最大数量的共线点.

我用Java做了这个问题.首先,我创建了一个检查线性的方法:

return (y1 - y2) * (x1 - x3) = (y1 - y3) * (x1 - x2);

然后我使用了三个for循环,这使我的算法O(n ^ 3).但我试图看看这是否可以减少到O(n ^ 2).

在网上搜索后,我发现我的实现与此处的内容非常相似.所以问题是我们如何才能提高复杂性.任何例子都会很棒.

这就是我最终做的事情:

int p = 2; 
for (int i = 0; i < points.lenght(); i++) {
    for (int j = i+1; j < points.length(); j++) {
        int count = 2;
        for (int k =0; i < points.length(); k++) {
            if (k == i || k == j)
                 continue;
            //use linearity function to check if they are linear...    
        }
        p = max(p,count);
    }
}

Answer 1

您可以使用两点之间的角度系数与 Ox 来解决此问题。例如，对于 3 个点： AB C。如果且仅当线 AB 和线 AC 与 Ox 线具有相同的角度系数时，它们共线。所以，这是我的伪代码：

// Type : an object to store information to use later
List<Type> res = new ArrayList<Type>();  
for (int i = 0; i < points.lenght(); i++) {
    for (int j = i+1; j < points.length(); j++) {
       double coefficient = CoeffiecientBetweenTwoLine(
                   line(points[i], points[j]), line((0,0), (0,1));
       res.add(new Type(points[i], points[j], coefficient);
    }
}

之后，您使用 QuickSort，根据 Coefficient 在 List 上方再次排序。并且任意系数相等，我们就可以知道哪些点是共线的。该算法的复杂度为O(N^2logN)（通过对包含元素的列表进行排序来控制O(N^2)，仅O(N^2)需要构建列表）。

@编辑： 那么当我们显示相等的系数时，我们如何知道有多少点共线？有很多方法可以解决这个问题。

• 在排序步骤中，当两个系数相等时，您可以按第一个参数（即该行中的哪个点）排序。例如。排序后，结果应该是（在这种情况下，如果 1 3 和 4 共线）：

  (1 3) (1 4) (3 4)

从上面的建筑中，您只需要看到 1 的条纹。在本例中，是 2。所以结果应该是 3。（始终是 k + 1）

• 使用公式： 因为总是等于的对数：n*(n-1)/2 。所以，你将拥有：n*(n-1)/2 = 3。你可以知道 n = 3 (n >= 0)。这意味着你可以在这里求解二次方程（但不是太难，因为你总是知道它有解，并且只需得到一个正解）

编辑2 上面的步骤知道有多少共线点是不正确的，因为在例如AB和CD是两条平行线的情况下（并且线AB与线CD不同），结果，它们仍然与Ox具有相同的系数。所以，我认为要解决这个问题，可以使用Union-Find数据结构来解决这个问题。步骤将是：

1. 重新排序角度系数 例如：(1 2 3 4) 共线，它们与 (5,6,7) 平行，点 8 位于其他位置。所以，排序后，结果应该是：

   (1 2) (1 3) (1 4) (2 3) (2 4) (5 6) (5,7) (6,7) 角度系数相等，但在两条不同的线上

   (1,5) (1, 6) .. // 将有一些对连接在两组平行线之间。(1, 8)

   (5, 8) (3, 8) .... // 随机顺序。因为不知道。

2. 使用并查数据结构连接树：从第二个元素开始迭代，如果看到它的角度系数与前一个元素相等，则连接自身并连接前一个元素。例如，

   (1,3) == (1,2) ：连接 1 和 2，连接 1 和 3。

   (1,4) == (1,3) ：连接 1 和 3，连接 1 和 4....

   (5,6) ：连接 2 和 4，连接 5 和 6。

   (5,7)：连接 5 和 7，连接 5 和 6 ...

   (1,8) ：不加入任何东西。(5,8)：不加入任何东西......

完成这一步后。您拥有的只是一棵多树，在每棵树中，都是一组共线的点。

在上面的步骤中，您会看到一些对多次加入。您可以简单地通过标记修复此问题，如果它们已经加入，请忽略以提高性能。

@ ：我认为这个解决方案不好，我只是通过我的大脑思考，背后没有真正的算法。那么，还有什么其他明确的想法，请告诉我。