为你的代码计算 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;
}