c - 这个 O(n^4) 的算法是可以避免的吗？

Question

免责声明:这不是作业问题。我什至不去上学。

#include <stdio.h>
void printIntersect(float, float, float, float);

int main(){
   int x, y, z, a;
   float slopes[] = {5, 9, 4/3.0f, 2/3.0f, 3};
   float inter[] = {3, 2, 1, 0, 5/3.0f};  

   for(x = 0; x < (sizeof(slopes) / sizeof(slopes[0])) - 1; x++)
       for(y = 1; y < (sizeof(slopes) / sizeof(slopes[0])); y++)
           for(z = 0; z < sizeof(inter) / sizeof(inter[0]); z++)
                  for(a = 0; a < sizeof(inter) / sizeof(inter[0]); a++)
                      if(slopes[x] != slopes[y])
                          printIntersect(slopes[x], slopes[y], inter[z], inter[a]);

   return 0;
}

void printIntersect(float m_one, float m_two, float b_one, float b_two){
    float m_final, b_final, x_intersect;

    m_final = m_one - m_two;
    b_final = b_two - b_one;

    if(m_final < 0 && b_final < 0)
        m_final *= -1.0f, b_final *= -1.0f;

    if (b_final != 0)
        x_intersect = b_final / m_final;
    else
        x_intersect = 0;  

        printf("The intersection of y = %.2fx %c %.2f and y = %.2fx %c %.2f is x = %.2f\n",
            m_one, (b_one < 0) ? '-' : '+', b_one, m_two, (b_two < 0) ? '-' : '+', b_two, x_intersect);


    return;
}

场景:我不确定我的一本 C 书中有一个练习。我从问题中得到的是我有两个数组:一个代表一条线的可能斜率，另一个代表所有可能的 y 截距。目标是使用斜率和截距与两条线的所有可能组合来找到它们的交点。我要忽略平行线和重复线(考虑到如果它们不能平行，它们无论如何都会被隐式忽略，那么它们就不可能是同一条线)。

假设这是前提(此时我真的不在乎，这只是一个练习)，我编写的程序使用了 4 个嵌套的 for 循环。你可以明白为什么这让我担心，但话又说回来，也许他们中的 4 个是必要的。

因为我不能有平行线，所以我从第一条线的斜率开始迭代斜率，然后迭代数组中的所有其他斜率作为第二条线的斜率。通过这种方式，我获得了所有可能的坡度组合。

截距是不同的，因为我可以有一行相同的截距，但它们仍然不同。因此，它们之间的迭代不需要考虑重复项。话虽这么说，我遍历截距数组的方式应该考虑到这两行中的每一对可能的对。

如果线不平行，我调用一个函数来打印 x 截距。

我的问题是，是否可以避免或至少简化这个 O(n^4) 的解决方案？你对处理这些数组有什么建议吗？

Answer 1

给定 a 斜率和 b 相交，您可以制作 a*b 线。有a*b choose 2 行。这大约是 a*b*a*b 的一半(它是 (a*b*(a*b-1)/2)。没有额外的信息，看来您必须检查所有这些 - 所以是的，您的算法确实是 O(a*a*b*b)。

编辑:让我们根据答案以不同的方式看待这个问题。给定 a 斜率和 b 相交，并通过组合它们制作 a*b 线，我们将有多少个交点？为简单起见，我们假设这组斜率是不同的。

这是一个不同于询问我们给了 n 行多少个交叉点的问题，因为这些行的构造方式不同。给定一个斜率，我们创建 b 平行线。接下来，我们创建另一条 b 平行线，其中没有一条平行于第一组线。重复 a 次。

在一组中，我们没有交叉点，因为它们都是平行的。

在两个集合之间，我们有多少个交集？一组中的线都不平行于另一组中的线，因此一组中的每条线将与第二组中的每条线相交一次。由于每个集合都有 b 行，因此任何两个集合之间都会有 b*b 个交集。

这里我们注意到所有这些线集也共享同一组 b 相交。因此，对于与当前相交线组相交的每一组附加线，您将添加 (b*b - b)*c = b*c*(b-1) 交点，其中 c 是已经包含的线组数，因为 b y 截距处的交点已经计算在内，所以我们只添加 b*(b - 1) 已经存在的每组线的交点。

所以我们有两个集合的初始 b^2，加上用于添加第三个集合的 b*(b - 1)*2，加上 b* (b - 1)*3 用于添加第四个等，直到 b*(b-1)*(a-1) 用于添加 a第组。即交集I的个数为:

I = b^2 + 2b(b-1) + 3b(b-1) + ... + (a-1)b(b-1)

我们可以将b^2重写为b + b(b-1):

I = b + b(b-1) + 2b(b-1) + ... + (a-1)b(b-1)

分解出最后一个a-1项中常见的b(b-1):

I = b + b(b-1)[1 + 2 + ... + (a-1)]

我们注意到从1到x的数字之和是x*(x+1)/2:

                (a-1)*a 
I = b + b(b-1)  ------- 
                   2

        a*(a-1)*b*(b-1)
  = b + ---------------
               2

        (a^2 - a)(b^2 - b)
  = b + ------------------
                2

    a^2*b^2 - a^2*b - a*b^2 + a*b + 2b
  = ----------------------------------
                    2

因此，无论您使用什么算法，您都将不得不生成那么多独立的输出片段，这确实比 a^2*b^2 少，但相差不大金额。