big-o开始使用big-o


备注

本节概述了big-o是什么,以及开发人员为什么要使用它。

它还应该提到big-o中的任何大型主题,并链接到相关主题。由于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毫秒)* n 0 )或100毫秒((100毫秒)* n 0 ) - 确切的值取决于所涉及的计算机的功能以及printf() 打印的内容。但由于这些因素不符合的大小改变a ,它们都不重要了大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 = 0return sum; 每次运行一次,少于n 次 - 我们忽略这些行。 sum += a[i] 运行多久并不重要 - 这是一个取决于计算机功率的系数 - 所以我们删除了该系数。因此,该函数是O(n)

如果存在多个代码路径,则通常根据最坏情况计算big-O。例如,即使这个函数也许可以立即退出,无论a 有多大(如果a[0]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;
}
 

什么是Big-O表示法?

Big-O表示法是用于谈论功能的长期增长率的符号。它经常用于算法分析,以讨论算法的运行时或空间复杂性等相关概念。

在常见用法中,使用big-O表示法来讨论算法的运行时如何按输入的大小进行缩放。例如,我们假设选择排序的运行时间为O(n 2 ),因为运行时是作为要排序的数组大小的函数的二次方增长。也就是说,如果您将输入的大小加倍,则选择排序的运行时间应该大约加倍。使用big-O表示法时,惯例是删除系数并忽略低阶项。例如,虽然技术上说二进制搜索在时间O(2 log 2 n + 17)中运行并没有错,但它被认为是糟糕的风格,并且最好在时间O(log n)中编写二进制搜索运行。

形式上,big-O表示法用于量化函数的长期行为。我们说f(n)= O(g)(在某些来源中有时表示为f(n)∈O(g(n)),如果有固定常数c和n 0 ,则f(n)≤c·g (N)对所有的n≥N 0。这个正式的定义解释了为什么我们不关心低阶项(它们可以通过使c更大并且增加n 0 )和常数因子(c项吸收它们)来归结。这种形式定义通常用于严格的算法分析,但很少用于口语。