big-o 为您的代码计算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 ⁰）或100毫秒（（100 ms）* n ⁰）-确切的值取决于所用计算机的电源以及要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（if a[0]is 0）都可能立即退出，但仍然存在导致第6行运行的情况a.length，所以它仍然是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;
}