大多数拥有计算机科学学位的人肯定知道大O代表什么。 它帮助我们衡量一个算法的可扩展性。

但我很好奇,你是如何计算或近似你的算法的复杂性的?


当前回答

如果你的成本是一个多项式,只保留最高次项,而不保留它的乘数。例如:

(O (n / 2) + 1) * (n / 2)) = O (n2/4 = O (n / 2) + n2/4) = O (n2)

注意,这对无穷级数不成立。对于一般情况,没有单一的方法,但对于一些常见情况,适用以下不等式:

O(log N) < O(N) < O(N log N) < O(N2) < O(Nk) < O(en) < O(n!)

其他回答

大O表示算法时间复杂度的上界。它通常与处理数据集(列表)一起使用,但也可以在其他地方使用。

下面是一些在C代码中如何使用它的例子。

假设我们有一个n个元素的数组

int array[n];

如果我们想要访问数组的第一个元素,这将是O(1)因为不管数组有多大,它总是需要相同的常数时间来获得第一项。

x = array[0];

如果我们想在列表中找到一个数字:

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

这是O(n)因为我们最多要遍历整个列表才能找到我们要的数。大O仍然是O(n),即使我们可能在第一次尝试中找到我们的数字并运行一次循环,因为大O描述了算法的上界(omega是下界,theta是紧界)。

当我们讲到嵌套循环时:

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

这是O(n²)因为对于外层循环的每一次循环(O(n))我们都必须再次遍历整个列表,所以n乘以后只剩下n²。

这仅仅是触及表面,但当你分析更复杂的算法时,涉及证明的复杂数学就会发挥作用。希望这至少能让你熟悉基本知识。

我想从另一个角度来解释Big-O。

Big-O只是用来比较程序的复杂性,也就是当输入增加时它们的增长速度有多快,而不是花在执行操作上的确切时间。

恕我直言,在大o公式中,你最好不要使用更复杂的方程(你可以坚持使用下图中的方程)。然而,你仍然可以使用其他更精确的公式(如3^n, n^3,…),但有时会误导!所以还是尽量简单为好。

我想再次强调,这里我们不想得到一个精确的算法公式。我们只想展示当输入增加时它是如何增长的并在这方面与其他算法进行比较。否则,您最好使用不同的方法,如基准测试。

将算法分解成你知道的大O符号,并通过大O运算符组合。这是我知道的唯一办法。

欲了解更多信息,请查看有关该主题的维基百科页面。

对于第一种情况,内部循环执行了n-i次,因此执行的总次数是i从0到n-1(因为小于,而不是小于或等于)的和。你得到最后n * (n + 1) / 2,所以O (n²/ 2)= O (n²)。

对于第二个循环,i在0到n之间。然后,当j严格大于n时执行内循环,这是不可能的。

熟悉我使用的算法/数据结构和/或快速分析迭代嵌套。难点在于,当您调用一个库函数时,可能会多次调用—您常常不确定是否在不必要的时候调用了函数,或者它们正在使用什么实现。也许库函数应该有一个复杂度/效率度量,无论是大O还是其他度量,都可以在文档或智能感知中得到。