2つの条件を持つループのbig O計算

Question

以下は、geeksforgeekからの最も近い対のポイントのコードスニペットです。

コメントに見られるように、関数はO（n^2）ではなく線形で実行されると言います。

それは第二のループは、一定の時刻に実行することができるからである。ここでは

for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j)

は私の質問です：

このループのために、それは「しない限り、とにかくn回で実行されますj "は大きすぎません。

いくつかの "j"のループ内で実行されないことはわかっていますが、 でもループは "n"回実行されます。

したがって、大きなO表記を計算するときは、 内部ループを実行するケースのみを気にする必要がありますか？

もしそうなら、この問題について説明する良い参考資料をお勧めしますか？

// A utility function to find the distance beween the closest points of 
// strip of given size. All points in strip[] are sorted accordint to 
// y coordinate. They all have an upper bound on minimum distance as d. 
// Note that this method seems to be a O(n^2) method, but it's a O(n) 
// method as the inner loop runs at most 6 times 
float stripClosest(Point strip[], int size, float d) 
{ 
    float min = d; // Initialize the minimum distance as d 

    qsort(strip, size, sizeof(Point), compareY); 

    // Pick all points one by one and try the next points till the difference 
    // between y coordinates is smaller than d. 
    // This is a proven fact that this loop runs at most 6 times 
    for (int i = 0; i < size; ++i) 
     for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j) 
      if (dist(strip[i],strip[j]) < min) 
       min = dist(strip[i], strip[j]); 

    return min; 
} 

http://www.geeksforgeeks.org/closest-pair-of-points/

Answer 1

私は "問題" を参照してくださいしないでください：内部ループは、ネストされたループOの全体を作り、O（1）、およびそれをn回実行されたで動作します（N） 。

については、 O（1）の内側のループは、「このループは最大6回実行されることが実証されています」というコードの主張に基づいています。あなたはそれがなぜそうであるかを説明するために誰にでも十分な情報を提供しておらず、主張をはるかに反駁していません。

Answer 2

ループの重要な部分は(strip[j].y - strip[i].y) < minです。 j < sizeの条件は、配列の境界を越えるのを止めることですが、もう1つの条件は複雑さにとって重要です。いずれかの条件に達するとループは終了するので、下限を作成するループを見るだけでよい。

ポイント間の垂直距離を確認しています。各点は以前よりも離れているので、距離が増えています。反復の回数は、この距離がminに達した時点（min <= d）に依存します。

これは、多くの点が単一の正方形内の点のない一対dより近くないことを考えると、水平方向に互いに隣接して配置された2つのddによって正方形内に収まることができる方法を尋ねると同じです。

これはlinked pageで返されるジオメトリの質問です。答えが8（または開始点を除いて7）であることがわかります。したがって、ループの反復回数は7回に過ぎず、内側ループの複雑さはO(1)です両方のループではO(n)です。

コメントには6回の反復がありますが、他の場所では7回と言われていますので、矛盾しますが、重要なことは定数であることです。