将算法从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);
    }
}

- add-semi-colons

---

你在这行代码 return (y1 - y2) * (x1 - x3) = (y1 - y3) * (x1 - x2); 中存在问题，因为这是一个赋值语句，而不是比较语句。 - phuclv

有一个O(n^2)的解决方案，但它基于点线对偶。对于原始平面中的每个点，您在对偶平面中创建一条线。在对偶平面中具有最大度数的点对应于通过最多点的原始平面中的线。这可以通过使用线安排在O(n^2)的时间内计算出来。 - Yu-Han Lyu

Answer 1

我来到了与@hqt的解决方案非常相似的地方，并想详细说明他们遗漏的细节。

如果它们的dx到dy比率（即斜率）相同，则此类的两个元素相等。

static class Direction {
    Direction(Point p, Point q) {
        // handle anti-parallel via normalization
        // by making (dx, dy) lexicographically non-negative
        if (p.x > q.x) {
          dx = p.x - q.x;
          dy = p.y - q.y;
        } else if (p.x < q.x) {
          dx = q.x - p.x;
          dy = q.y - p.y;
        } else {
          dx = 0;
          dy = Math.abs(p.y - q.y);
        }
    }

    public boolean equals(Object obj) {
        if (obj==this) return true;
        if (!(obj instanceof Direction)) return false;
        final Direction other = (Direction) obj;
        return dx * other.dy == other.dx * dy; // avoid division
    }

    public int hashCode() {
        // pretty hacky, but round-off error is no problem here
        return dy==0 ? 42 : Float.floatToIntBits((float) dx / dy);
    }

    private final int dx, dy;
}

现在通过循环遍历所有点对（复杂度为O(n*n)），填充一个Guava的Multimap<Direction, PointPair>。遍历所有键（即方向），并通过并查集算法处理List<PointPair>。找到的分区是共线点对的集合。如果有k个共线点，则会找到包含它们所有点对的集合。

由于使用了并查集算法，因此复杂度为O(n*n*log(n))，避免排序没有帮助。

- maaartinus

Answer 2

您可以使用两点之间与Ox轴的角系数来解决这个问题。例如，对于3个点：A B 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在系数上再次排序以上List。 如果任何系数相等，则我们可以知道哪些点共线。 此算法的复杂度为O（N ^ 2logN）（由于对具有O（N ^ 2）元素的列表进行排序而主导，仅需O（N ^ 2）来构建列表）。

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

- 在排序步骤中，当两个系数相等时，可以按第一个参数（表示该行中的哪个点）进行排序。例如，在排序后，结果应为（在这种情况下，如果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）。 这意味着您可以在这里解决二次方程（但不会太困难，因为您总是知道它有解，并且只需获得一个正解） Edit 2 上述步骤用于确定有多少条共线点是不正确的，因为例如，A B和C D是两条平行线（线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)：不连接任何东西...

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

在上一步中，您会发现有些对被连接了多次。您可以通过标记来简单地修复这个问题，如果它们已经连接，则忽略以提高性能。

@：我认为这个解决方案不好，我只是凭借自己的思维方式做出来的，并没有真正的算法支持。因此，如果有任何其他清晰的想法，请告诉我。

- hqt

---

你能解释一下 CoeffiecientBetweenTwoLine 和 line 方法吗？我不太确定发生了什么。谢谢。另外，我找到了以下内容：https://github.com/rubymaniac/coursera/blob/master/algorithmsI/week3/programming_assignment/src/Fast.java - add-semi-colons

你的算法还没有完成。得到两个相等的系数意味着存在共线点，仅此而已。目前还没有明显的方法可以找出有多少个共线点。想象一下，如果一个给定的“系数”出现了4次，这是什么意思？ - maaartinus

@maaartinus，我已经编辑了我的帖子，以了解如何解决您提到的问题 :) - hqt

现在想象一组点：{(0,1), (0,2), (0,3), (10,1), (10,2)}。使用修正后的公式，对于方向向量(0,1)，您将得到3*2/2 + 2*1/2 = 4个元素。这是因为这些点位于两条平行线上。 - maaartinus

@hqt 我认为你的算法将平行线视为共线。 - Vikram Bhat

Answer 3

请尝试以下操作

    //just to create random 15 points
    Random random = new Random();
    ArrayList<Point> points = new ArrayList<Point>();
    for(int i = 0; i < 15; i++){
        Point p = new Point(random.nextInt(3), random.nextInt(3));
        System.out.println("added x = " + p.x + " y = " + p.y);
        points.add(p);
    }

    //code to count max colinear points
    int p = 0;
    for(int i = 0; i < points.size() -1; i++){
        int colinear_with_x = 1;
        int colinear_with_y = 1;
        for(int j = i + 1; j < points.size(); j++){
            if(points.get(i).x == points.get(j).x){
                colinear_with_x++;
            }
            if(points.get(i).y == points.get(j).y){
                colinear_with_y++;
            }
        }
        p = max(p,colinear_with_x,colinear_with_y);
    }

- Malav

Answer 4

一种依赖于良好哈希映射的方法：

使用线性方程（定义一条直线）作为键，以便您在该直线上拥有一个映射。

map<key=(vector, point), value=quantity> pointsOnLine

其中向量和点定义了由两个点确定的线性函数。

然后你要迭代所有n个点：

maxPoints = 2
for i=1 to n
  for j=i+1 to n
    newKey = lineParametersFromPoints(point[i], point[j])
    if pointsOnLine.contains(newKey)
      pointsOnLine[key] += 1
      if maxPoints < pointsOnLine[key]
        maxPoints = pointsOnLine[key]
    else
      pointsOnLine.add(key)
      pointsOnLine[key] = 2

maxPoints 现在包含最大共线点的数量。

请注意（这可能是最重要的），map 的哈希比较函数必须检查两条线是否代表相同的线性函数，即使向量是反平行的或者两条线上的点不相同（但一个满足另一个方程）。

当然，这种方法严重依赖于 map 具有快速访问和插入时间。

- B. M. Knecht

Answer 5

算法 :- 可以在O(N^2*logN)时间内完成的简单算法 :-

1. 选择一个点p。
2. 计算从p到所有其他点的斜率
3. 按斜率对点进行排序
4. 扫描排序后的数组，检查具有相同斜率值的最大连续点数
5. 最大值+1是包括p的共线点的最大点数。
6. 对所有点执行1到5，并找到找到的最大共线点数

时间复杂度：斜率计算为O(N)，排序为O(NlogN)，所有N个点的时间复杂度为O(N^2*logN)。

空间复杂度：斜率和点的空间复杂度为O(N)

- Vikram Bhat