大O为代码片段

Question

你好，这是一段时间的罪我已经使用大O符号，所以我有点生疏。我知道有1个循环，循环n次是O（n），并且有1个循环在循环n次的另一个循环内循环n次是O（n^2）。

但是，在下面的代码片段中，我有一个循环，循环n次，并在该循环内循环n-i次。

对于这段代码，最坏的和最好的O符号是什么？

最糟糕的是它没有发现碰撞的情况下运行，最好的情况是两个第一个矩形之间有碰撞。

class TestClass 
{ 
    bool Run(List<Rectangle> R) 
    { 
     var b = false; 
     var i = 0; 
     var n = R.Count; 
     var j = 0; 
     while ((i < n-1) && !b) 
     { 
      j = i + 1; 
      while (j<n && !b) 
      { 
       if ((R[i].x >= R[j].x - R[i].w) && (R[i].x <= R[j].x + R[j].w)) 
        if ((R[i].y <= R[j].y + R[i].h) && (R[i].y >= R[j].y - R[j].h)) 
         b = true; 
       j++; 
      } 
      i++; 
     } 

     return b; 
    } 
} 

public class Rectangle 
{ 
    public int x; 
    public int y; 
    public int w; 
    public int h; 
} 

Answer 1

您的实际最坏情况运行时间是n X n/2 =n²/ 2。抛弃常量，它是O（n²）

Answer 2

作为一个评论者指出，大澳始终是对最坏的情况下，如果增加R.Count的价值往往会令你的最坏的情况在大于n的速率增长* log（n），你会进入n²的领域。

由于你有一个双嵌套的while循环，并且不需要额外的方法调用，所以我一眼就知道它是O（n²）。

然而，在这种情况下，由于i和j从不增加，以及n从不递减，你的循环都是基于i或j小于n，此功能将是（根据您的if声明退出的时候了），否则它永远不会。

O(infinity)? 

编辑

好了，现在你递增。其中，N *（NI）位基本上平均到N *（N/2）每次运行时（不是平均的所有运行，但是对于每个运行而言平均为）。这是因为当你在外部循环中移动时，你会做（n，n-1，n-2，...，3，2，1）内部循环。如果折叠此设置本身，你可以很容易总结的回路数：

n + 1 == n + 1 
(n-1) + 2 == n + 1 
(n-2) + 3 == n + 1 
... 

所以，你最终与正的N/2个实例+ 1，其中就出来（N²+ N）/ 2。从大O的角度来看，这与n²相同。