この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の本の1つでは、私には分かりません。私が問題にしたのは、2つの配列を持つことでした：1つはラインの可能な傾きを表し、もう1つはすべての可能なyインターセプトを表します。目的は、交差点を見つけるために、2つの線でスロープと切片のすべての可能な組み合わせを使用することでした。私は平行線と重複する行を無視していました（たとえ平行でない場合は暗黙のうちに無視され、同じ行になることはありません）。

これが前提である（と私は実際には気にしませんが、これは単なる練習です）、私が書いたプログラムは4個のforループを使用しています。それがなぜ私に関係するのか分かりますが、もう一度、おそらく4つが必要かもしれません。

私は平行線を持つことができないので、最初の線で開始してスロープを反復し、2番目の線のスロープとして配列の他のすべてのスロープを反復処理します。それは私が斜面のすべての可能な組み合わせを得るこの方法です。

私は同じインターセプトのラインを持つことができ、それらはまだ異なっているので、インターセプトは異なります。だから、それらの間の反復は重複を説明する必要はありません。つまり、インターセプトの配列を反復する方法は、その2つの行の可能なすべてのペアを説明する必要があります。

行が平行でない場合は、x切片を出力する関数を呼び出します。

私の質問は、このO（n^4）解決策は回避できましたか、少なくとも簡略化できましたか？これらのような配列の処理に関するヒントはありますか？

Answer 1

すでに、2番目のループの開始インデックスを変更することでループを半分にすることができます。

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

を与える

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

へ

for (y = 1, ...) 

私はまたjxhが指摘したように、slopesが重複したエントリが含まれていても、平等のチェックを削除しました。あなたがO（n）の重複を取り除くことができるので、私はこれを行いました。

もちろん、アルゴリズムの全体的な複雑さは変わりませんが、実行時に役立ちます。

Answer 2

aスロープとbが交わると、a*b行にすることができます。 a*b choose 2行のペアがあります。 。。の質問を見てみましょう：ので、あなたのアルゴは確かO(a*a*b*b)あるうん

EDIT - これは（それが（a*b*(a*b-1)/2）で追加の情報を与えられていない、あなたがそれらのすべてをチェックするために持っているようにそれはそうa*b*a*bな限り約半分でありますスロープとbが交差し、それらを組み合わせてa*bラインを作ると、いくつの交差があるでしょうか？簡単にするために、スロープのセットは別々であるとしましょう。

これは、我々が原因のラインが構築されている方法のnラインを、与えているどのように多くの交差尋ねるとは異なる問題です。斜面を1つ与えると、bの平行線が作成されます。次のようにすると、別のbの平行線が作成されますが、いずれも最初の線のセットと平行ではありません。繰り返すa回。彼らはすべて並列しているので、

は、1セットの中で、私たちは何の交差点を持っていません。 2つのセットの間

、私たちはどのように多くの交差点がありますか？一方のセットの各行は、他方のセットの行と平行ではないため、1つのセットの各行は、2番目のセットの各行と1回交差します。各セットにb行があるので、任意の2つのセットの間にはb*bの交差点があります。

ここでは、行のすべてのこれらのセットはまた、b交差の同じセットを共有することに注意してください。したがって、現在の交差ラインのセットと交差する場合は、のy切片の交差点が既に考慮されているため、(b*b - b)*c = b*c*(b-1)交差点を追加します。ここで、cはすでに含まれているラインのセット数です。 、すでにそこにある線の集合ごとにb*(b - 1)の交点を追加するだけです。

だから我々はa番目のセットを追加するためのb*(b-1)*(a-1)まで、など、第四を追加するための第三、プラスb*(b - 1)*3を追加するための2つのセット、プラスb*(b - 1)*2のための私たちの最初のb^2を持っています。つまり、交差点Iの数があるさ：

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

我々は再書き込みが可能b^2b + b(b-1)として：最後a-1という点で共通b(b-1)アウト

I = b + b(b-1) + 2b(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未満の出力の多くの別々の部分、つまり、ではなく、かなりの量で生成する必要があるとしています。

Answer 3

私はあなたが離れO（M X Y ）（M明確な斜面とYの異なるインターセプト）から得ることができるとは思わないが、彼らは最初に別個であるように、あなたの配列をフィルタリングすることができます。これにより、入力に多数の重複が含まれている場合に、プログラムの実行速度が向上します。また、重複するy切片を削除せずに、重複した線の交点を生成して印刷することもできます。

だから、あなたが入力を並べ替え、その後、重複を削除することができqsortを使用。ソートはO（N X ログ N）であるので、それはあなたのアルゴリズムの全体的な複雑さに影響を与えるdoes't（と多くの重複がある場合には、それをスピードアップ）。ハッシュテーブルを使用して重複をより早く排除することは可能ですが、標準Cライブラリではハッシュテーブルを提供していません（1つを見つけるか、自分で実装する必要があります）。

#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に相談することができます。