為你的程式碼計算 Big-O

計算你編寫的過程的 Big-O 值的一種方法是在給定輸入大小 n 的情況下確定哪個程式碼行在函式中執行的次數最多。一旦你擁有了這個數字，就可以取出除了增長最快的條件之外的所有條款並擺脫係數 - 這是你函式的 Big-O 表示法。

例如，在此函式中，每行只執行一次，並且無論 a 有多大，都會執行相同的時間：

int first(int[] a){
   printf("Returning the first element of a");
   return a[0];
}

函式本身可能需要 1 毫秒（（1 ms）* n 0 ）或 100 毫秒（（100 ms）* n 0 ） - 確切的值取決於所涉及的計算機的功率以及 printf() 的列印內容。但由於這些因素不會隨著 a 的大小而變化，因此對於 Big-O 計算並不重要 - 它們是常數係數，我們將其刪除。因此，該函式的 Big-O 值為 O(1) 。

在這個函式中，第 3 行（sum += a[i];）對 a 中的每個元素執行一次，總共 a.length（或 n ）次：

int sum(int[] a){
   int sum = 0;
   for (int i = 0; i < a.length; i++){
        sum += a[i];
   }
   return sum;
}

宣告 i++和 i < a.length 每次也執行 n 次 - 我們可以選擇那些線，但我們沒有必要。另外，int sum = 0;，int i = 0 和 return sum; 每次執行一次，少於 n 次 - 我們忽略這些行。sum += a[i] 執行多長時間並不重要 - 這是一個取決於計算機功率的係數 - 所以我們刪除了該係數。因此，該函式是 O(n) 。

如果存在多個程式碼路徑，則通常根據最壞情況計算 big-O。例如，即使這個函式也許可以立即退出，無論 a 有多大（如果 a[0] 是 0），仍然存在導致第 6 行執行 17 次的情況，所以它仍然是 O(n)：

int product(int[] a){
    int product = 0;
    for (int i = 0; i < a.length; i++){
        if (a[i] == 0)
            return 0;
        else 
            product *= a[i];
    }
    return product;
}