这个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

好吧，我们已经可以通过更改第二个循环的起始索引来将循环减半。

for (y = 1, ...)

到

for (y = x + 1; ...)

给予

for (x = 0; x < (sizeof(slopes) / sizeof(slopes[0])) - 1; x++)
    for (y = x + 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++)
                printIntersect(slopes[x], slopes[y], inter[z], inter[a]);

我还删除了相等性检查，尽管正如 jxh 指出的那样，slopes可能包含重复的条目。好吧，我这样做是因为你可以在 O(n) 时间内删除重复项。

当然，这不会改变算法的整体时间复杂度，但它应该有助于运行时。