大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²相同。