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

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

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

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

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

大O符号很有用，因为它很容易使用，并且隐藏了不必要的复杂性和细节(对于一些不必要的定义)。求解分治算法复杂性的一种好方法是树法。假设你有一个带有中值过程的快速排序版本，所以你每次都将数组分割成完美平衡的子数组。

现在，构建一个与所使用的所有数组对应的树。根结点有原始数组，根结点有两个子数组。重复此步骤，直到底部有单个元素数组。

由于我们可以在O(n)时间内找到中位数，并在O(n)时间内将数组分成两部分，因此在每个节点上所做的功为O(k)，其中k是数组的大小。树的每一层都包含(最多)整个数组，所以每层的功是O(n)(子数组的大小加起来是n，因为每层有O(k)，我们可以把它加起来)。树中只有log(n)层，因为每次我们将输入减半。

因此，我们可以将功的上限设为O(n*log(n))。

然而，大O隐藏着一些我们有时不能忽视的细节。考虑计算斐波那契数列

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

假设a和b在Java中是biginteger或者其他可以处理任意大数字的东西。大多数人会毫不犹豫地说这是一个O(n)算法。理由是，在for循环中有n次迭代，而O(1)工作在循环的一侧。

但是斐波那契数列很大，第n个斐波那契数列是n的指数级，所以仅仅是存储它就需要n个字节。对大整数执行加法将花费O(n)个工作量。所以在这个过程中所做的总功是

一加二加三……+ n = n(n-1)/2 = O(n)

所以这个算法在二次时间内运行!

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

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

假设我们有这样一个函数(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.

我将尽最大努力在这里简单地解释它，但请注意，这个主题需要我的学生几个月才能最终掌握。你可以在《Java中的数据结构和算法》一书的第2章中找到更多信息。

---

没有机械程序可以用来获得BigOh。

作为“烹饪书”，要从一段代码中获得BigOh，首先需要意识到您正在创建一个数学公式来计算给定一定大小的输入执行了多少步计算。

目的很简单:从理论的角度比较算法，而不需要执行代码。步数越少，算法越快。

例如，假设你有这样一段代码:

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

这个函数返回数组中所有元素的和，我们想创建一个公式来计算该函数的计算复杂度:

Number_Of_Steps = f(N)

我们有f(N)，一个计算步数的函数。函数的输入是要处理的结构的大小。这意味着该函数被调用，如:

Number_Of_Steps = f(data.length)

参数N接受数据。长度值。现在我们需要函数f()的实际定义。这是从源代码中完成的，其中每个感兴趣的行编号从1到4。

有很多方法来计算BigOh。从这一点开始，我们将假设每个不依赖于输入数据大小的句子都需要常数C个计算步骤。

我们将添加函数的步数，局部变量声明和return语句都不依赖于数据数组的大小。

这意味着第1行和第4行每一行都要走C步，函数是这样的:

f(N) = C + ??? + C

下一部分是定义for语句的值。请记住，我们正在计算计算步骤的数量，这意味着for语句体被执行N次。这就相当于把C加N次

f(N) = C + (C + C + ... + C) + C = C + N * C + C

没有机械规则来计算for语句体执行了多少次，您需要通过查看代码的操作来计算。为了简化计算，我们忽略了for语句的变量初始化、条件和增量部分。

为了得到实际的BigOh，我们需要函数的渐近分析。大致是这样做的:

去掉所有常数C。 由f()得到多项式的标准形式。 对多项式的项进行除法，并按增长率对它们排序。 保留N趋于无穷时变大的那一个。

f()有两项:

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

去掉所有C常数和冗余部分:

f(N) = 1 + N ^ 1

由于最后一项是当f()接近无穷大时变大的项(考虑极限)，这是BigOh参数，sum()函数的BigOh为:

O(N)

---

有一些技巧可以解决一些棘手的问题:尽可能使用求和。

作为一个例子，这段代码可以很容易地使用求和来求解:

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

首先需要询问的是foo()的执行顺序。虽然通常是O(1)，但你需要问你的教授。O(1)表示(几乎，大部分)常数C，与N大小无关。

第一句中的for语句很复杂。当索引结束于2 * N时，增量为2。这意味着第一个for只执行了N步，我们需要将计数除以2。

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

第二句话更棘手，因为它取决于i的值。看一下:索引i取的值:0,2,4,6,8，…， 2 * N，第二个用于执行:N乘以第一个，N - 2是第二个，N - 4是第三个……直到N / 2阶段，在这个阶段，第二个for语句永远不会被执行。

在公式上，这意味着:

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

同样，我们在计算步数。根据定义，每个求和都应该从1开始，以大于等于1的数结束。

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(我们假设foo()是O(1)，并采取C步。)

这里有一个问题:当i取值N / 2 + 1向上时，内部求和以负数结束!这是不可能的，也是错误的。我们需要把和式分成两部分，当i取N / 2 + 1时是关键点。

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

因为关键时刻i > N / 2，内部的for不会被执行，我们假设它的主体上有一个恒定的C执行复杂度。

现在可以使用一些恒等规则来简化求和:

求和(w从1到N)(C) = N * C 求和(w from 1 to N)(A (+/-) B) =求和(w from 1 to N)(A)(+/-)求和(w from 1 to N)(B) 求和(w从1到N)(w * C) = C *求和(w从1到N)(w) (C是一个常数，与w无关) 求和(w从1到N)(w) = (N * (N + 1)) / 2

应用一些代数运算:

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

BigOh是:

O(N²)

对于代码A，外层循环将执行n+1次，“1”时间表示检查i是否仍然满足要求的过程。内循环运行n次，n-2次....因此，0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²)。

对于代码B，虽然内部循环不会介入并执行foo()，但内部循环将执行n次，这取决于外部循环的执行时间，即O(n)