优化算法（N^3）为O（n^2）

假设你给出的点集在二维空间以及如何我们可以得到最大的共线点数。

我在Java中做了这个问题。首先我创建用于检查线性度的方法，包括：

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

然后我使用了三个for环路这使得我的算法为O（n^3）。但我试图看看这是否可以减少到O（n^2）。

在网上搜索后，我发现我的实现非常类似于什么here。所以问题是我们如何才能提高复杂性。任何例子都会很棒。

这是我落得这样做：

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); 
    } 
}

来源

2014-01-10 Null-Hypothesis

你在行'return（y1 - y2）*（x1 - x3）=（y1 - y3）*（x1 - x2）中有问题;'因为这是一个赋值，而不是比较 –

还有一个O n^2）解决方案，但它是基于点线二元性的。对于原始平面中的每个点，都可以在双平面中创建一条线。双平面中度数最大的点对应于通过最大点数的原始平面中的线。这可以通过使用线的排列在O（n^2）时间内计算。 –

你可以用两个点之间的角系数与牛年来解决这个问题。例如，对于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，再次在基于系数的列表基础上进行排序。而任何系数相等，我们可以知道哪些点是共线的。该算法的复杂度为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 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）... //随机顺序。因为不知道。
使用联盟查找数据结构来连接树：从第二个元素开始迭代，如果你看到它的角系数等于与以前的，加入自己和同前面。例如，

（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）：不加入任何东西...

完成该步骤后。你所拥有的只是一棵多树，在每棵树中，是一组共点，它们是共线的。

上面的步骤中，您会看到有些对是多次加入的。你可以简单地通过标记来解决这个问题，如果他们已经加入，忽略以提高性能。

@：我觉得这个方案不好，我只是通过我的大脑思维，不是一个真正的算法背后做。所以，其他任何明确的想法，请告诉我。

来源

2014-01-10 01:42:47 hqt

你能解释一下CoeffiecientBetweenTwoLine和line方法不是真的知道那里发生了什么。谢谢，我还发现以下：https://github.com/rubymaniac/coursera/blob/master/algorithmsI/week3/programming_assignment/src/Fast.java –

你的算法还没有完成。获得两个相等的系数意味着有共线点，就是这样。没有明显的方法来找出多少。设想一个给定的“系数”出现4次，这是什么意思？ – maaartinus

@maaartinus我编辑了我的帖子，知道如何解决你提到的问题:) – hqt

我来到非常相似@ 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>。遍历所有密钥（即方向）并通过union find algorithm处理List<PointPair>。找到的分区是共线点对的集合。如果共线点有k，那么你会发现一组包含它们的所有对。

由于联合查找算法，复杂度为O(n*n*log(n))，避免排序没有帮助。

来源

2014-01-10 02:31:27 maaartinus

算法： - 简单的算法，它可以做到在O(N^2*logN)： -

选择一个点p。

根据斜坡查找从对斜率的所有其他点

点排序

扫描排序后的数组，以检查用于与相同斜率值的最大连续点

最大值+ 1是最大的点共线与对包括在内。

做1至5的所有点，找到最大共线点发现

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

空间的复杂性：O(N)的斜坡和点

来源

2014-01-10 06:42:08

是的。我认为这个解决方案很好，很明亮:) – hqt

试试下面

//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); 
    }

来源

2014-01-10 11:16:41 Malav

的一种方法，在很大程度上依赖一个好的哈希图：

由于键使用线性方程（定义一条线），这样你就可以得到一张沿

的地图

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则包含共线点的最大数量。

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

这种方法当然很大程度上依赖于具有快速访问和插入时间的地图。

来源

2014-01-11 02:18:50

优化算法（N^3）为O（n^2）

回答

相关问题