不要忘记考虑空间的复杂性，如果内存资源有限，这也是一个值得关注的问题。例如，你可能听到有人想要一个常数空间算法，这基本上是说算法所占用的空间量不依赖于代码中的任何因素。

有时，复杂性可能来自于某个东西被调用了多少次，循环执行的频率，内存分配的频率，等等，这是回答这个问题的另一部分。

最后，大O可以用于最坏情况、最佳情况和摊销情况，其中通常用最坏情况来描述算法可能有多糟糕。

看到这里的答案，我想我们可以得出这样的结论:我们大多数人确实通过观察它和使用常识来近似算法的顺序，而不是像我们在大学里认为的那样用主方法来计算它。 说了这么多，我必须补充一点，即使教授也鼓励我们(后来)实际思考，而不是仅仅计算。

我还想补充一下如何对递归函数进行处理:

假设我们有这样一个函数(scheme code):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

递归地计算给定数字的阶乘。

第一步是尝试并确定函数体的性能特征，只是在这种情况下，在函数体中没有做任何特殊的事情，只是一个乘法(或返回值1)。

所以主体的性能是:O(1)(常数)。

接下来尝试确定递归调用的数量。在这种情况下，我们有n-1个递归调用。

所以递归调用的性能是:O(n-1)(阶为n，因为我们抛弃了无关紧要的部分)。

然后把这两个放在一起，你就得到了整个递归函数的性能:

1 * (n-1) = O(n)

Peter, to answer your raised issues; the method I describe here actually handles this quite well. But keep in mind that this is still an approximation and not a full mathematically correct answer. The method described here is also one of the methods we were taught at university, and if I remember correctly was used for far more advanced algorithms than the factorial I used in this example. Of course it all depends on how well you can estimate the running time of the body of the function and the number of recursive calls, but that is just as true for the other methods.

大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-Oh复杂化并不是解决办法， 这是程序员(或者至少是像我这样的人)寻找的。

Big Oh(简而言之)

function f(text) {
  var n = text.length;
  for (var i = 0; i < n; i++) {
    f(text.slice(0, n-1))
  }
  // ... other JS logic here, which we can ignore ...
}

上面的大写哦是f(n) = O(n!)其中n表示输入集中的条目数， f表示每一项所做的操作。

Big-Oh符号是算法复杂度的渐近上界。 在编程中:假设的最坏情况所花费的时间， 或假设逻辑的最大重复计数，为输入的大小。

计算

记住(从上面的意思);我们只需要受N(输入大小)影响的最坏情况时间和/或最大重复次数， 然后再看一下(公认答案的)例子:

for (i = 0; i < 2*n; i += 2) {  // line 123
    for (j=n; j > i; j--) {     // line 124
        foo();                  // line 125
    }
}

Begin with this search-pattern: Find first line that N caused repeat behavior, Or caused increase of logic executed, But constant or not, ignore anything before that line. Seems line hundred-twenty-three is what we are searching ;-) On first sight, line seems to have 2*n max-looping. But looking again, we see i += 2 (and that half is skipped). So, max repeat is simply n, write it down, like f(n) = O( n but don't close parenthesis yet. Repeat search till method's end, and find next line matching our search-pattern, here that's line 124 Which is tricky, because strange condition, and reverse looping. But after remembering that we just need to consider maximum repeat count (or worst-case time taken). It's as easy as saying "Reverse-Loop j starts with j=n, am I right? yes, n seems to be maximum possible repeat count", so: Add n to previous write down's end, but like "( n " instead of "+ n" (as this is inside previous loop), and close parenthesis only if we find something outside of previous loop.

搜索完成了!为什么?因为第125行(或之后的任何行)与我们的搜索模式不匹配。 现在我们可以关闭任何圆括号(在我们的记录中左开)，结果如下:

f(n) = O( n( n ) )

试着进一步缩短“n(n)”部分，比如:

N (N) = N * N = n2 最后，用Big Oh符号来包装它，就像O(n2)或O(n²)一样，没有格式。

如果您希望根据经验而不是通过分析代码来估计代码的顺序，您可以插入一系列不断增加的n值，并为代码计时。在对数刻度上绘制你的时间。如果代码是O(x^n)，值应该落在斜率为n的直线上。

这比只研究代码有几个优点。首先，您可以看到您是否在运行时接近其渐近顺序的范围内。此外，您可能会发现一些您认为是O(x)阶的代码实际上是O(x^2)阶的代码，例如，因为花在库调用上的时间。

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

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