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）中的重複項。

當然這並不會改變算法的整體時間複雜度，但它應該有助於運行時。

Answer 2

鑑於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的數量是：在過去的a-1條款

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

因子出公共b(b-1)：

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)[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的許多獨立的部分，而不是由一個顯著量。

Answer 3

我不相信你可以從Ø遠（M X Y ）（M不同的斜率和y軸截距不同），但讓他們在不同的第一您可以篩選陣列。這允許您的程序在輸入包含許多重複的情況下運行得更快。此外，如果不刪除重複的y截距，也可能會生成並打印重複的線交點。

因此，使用qsort您可以對輸入進行排序，然後刪除重複項。由於排序是O，所以它不會影響算法的整體複雜度（並且在有很多重複的情況下加速它）。使用哈希表可以更快地消除重複項，但標準C庫不提供一個（您必須自己找到一個或實現一個）。

#define ARRAY_SZ(x) (sizeof(x)/((void *)x == &x ? sizeof(x[0]) : 0)) 

static int is_equal_float (float a, float b) { /*...*/ } 

static int cmp_float (const void *a, const void *b) { 
    float af = *(const float *)a; 
    float bf = *(const float *)b; 
    if (is_equal_float(af, bf)) return 0; 
    return (af > bf) - (af < bf); 
} 

/* ... */ 
qsort(slopes, ARRAY_SZ(slopes), sizeof(slopes[0]), cmp_float); 
qsort(inter, ARRAY_SZ(inter), sizeof(slopes[0]), cmp_float); 

for (x = 0, y = 1; y < ARRAY_SZ(slopes) - 1; y++) 
    if (slopes[y] != slopes[x]) slopes[++x] slopes[y]; 
for (z = 0, a = 1; a < ARRAY_SZ(inter) - 1; a++) 
    if (inter[z] != inter[a]) inter[++z] slopes[a]; 
M = x+1; 
Y = z+1; 

for (x = 0; x < M - 1; x++) 
    for (y = x + 1; y < M; y++) 
     for (z = 0; z < Y; z++) 
      for (a = 0; a < Y; a++) 
       printIntersect(slopes[x], slopes[y], inter[z], inter[a]); 

我粉飾如何比較float S，但你可以對如何做到這一點在滿足應用程序的需求的方式解答諮詢Most effective way for float and double comparison。