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

我将尽最大努力在这里简单地解释它，但请注意，这个主题需要我的学生几个月才能最终掌握。你可以在《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²)

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

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

假设我们有这样一个函数(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(1)时间内完成，即在与输入大小无关的时间内完成。C语言中的这些基本操作由

算术运算(例如+或%)。 逻辑操作(如&&)。 比较操作(例如，<=)。 结构访问操作(例如A[i]这样的数组索引，或指针后跟 使用->操作符降低)。 简单的赋值，例如将值复制到变量中。 调用库函数(例如，scanf, printf)。

要证明这一原理，需要对典型计算机的机器指令(基本步骤)进行详细研究。所描述的每一个操作都可以用少量的机器指令来完成;通常只需要一个或两个指令。 因此，C语言中的几种语句可以在O(1)时间内执行，也就是说，在与输入无关的某个常数时间内执行。这些简单的包括

表达式中不涉及函数调用的赋值语句。 读语句。 编写不需要调用函数来计算参数的语句。 跳转语句有break、continue、goto和return表达式 表达式不包含函数调用。

在C语言中，许多for循环是通过将索引变量初始化为某个值和来形成的 在每次循环中对该变量加1。for循环结束于 指数达到某个极限。例如，For循环

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

使用索引变量i。它在循环和迭代中每一次都使i增加1 当I达到n−1时停止。

然而，目前，我们只关注for循环的简单形式，其中最终值和初始值之间的差值除以索引变量的增量，告诉我们循环了多少次。这个计数是准确的，除非有办法通过跳转语句退出循环;在任何情况下，它都是迭代次数的上限。

例如，For循环迭代((n−1)−0)/1 = n−1次， 由于0是i的初始值，n−1是i达到的最大值(即当i 到达n−1时，循环停止，当I = n−1)时不发生迭代，并添加1 在循环的每一次迭代中。

In the simplest case, where the time spent in the loop body is the same for each iteration, we can multiply the big-oh upper bound for the body by the number of times around the loop. Strictly speaking, we must then add O(1) time to initialize the loop index and O(1) time for the first comparison of the loop index with the limit, because we test one more time than we go around the loop. However, unless it is possible to execute the loop zero times, the time to initialize the loop and test the limit once is a low-order term that can be dropped by the summation rule.

---

现在想想这个例子:

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

我们知道直线(1)花费O(1)时间。显然，我们循环了n次 我们可以用在线上得到的上限减去下限来确定 (1)再加1。由于主体，行(2)，花费O(1)时间，我们可以忽略 增加j的时间和比较j与n的时间，两者都是O(1)。 因此，行(1)和行(2)的运行时间是n和O(1)的乘积，即O(n)。

类似地，我们可以限制由行组成的外部循环的运行时间 (2)到(4)，即

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

我们已经建立了行(3)和行(4)的循环花费O(n)时间。 因此，我们可以忽略O(1)时间来增加i，并测试i是否< n in 每次迭代，得出每次外循环迭代花费O(n)时间。

外部循环的初始化i = 0和条件的(n + 1)st检验 i < n同样需要O(1)次，可以忽略。最后，我们观察到我们走了 绕外循环n圈，每次迭代花费O(n)时间，得到总数 O(n²)运行时间。

---

一个更实际的例子。

经常被忽视的是算法的预期行为。它不会改变你的算法的大o，但它确实与“过早优化.. ..”的声明有关

你的算法的预期行为是——非常简单——你期望你的算法在你最有可能看到的数据上工作的速度有多快。

例如，如果你在一个列表中搜索一个值，它是O(n)，但如果你知道你看到的大多数列表都有你的值在前面，你的算法的典型行为会更快。

为了真正确定它，你需要能够描述你的“输入空间”的概率分布(如果你需要对一个列表排序，这个列表已经被排序的频率是多少?有多少次是完全相反的?多长时间进行一次排序?)这并不总是可行的，但有时你知道。

至于“如何计算”大O，这是计算复杂性理论的一部分。对于一些(许多)特殊的情况，您可能会使用一些简单的启发式方法(例如为嵌套循环乘以循环计数)，特别是当您想要的只是任何上限估计时，并且您不介意它是否过于悲观——我猜这可能就是您的问题的内容。

如果你真的想回答任何算法的问题你能做的最好的就是应用这个理论。除了简单的“最坏情况”分析，我发现平摊分析在实践中非常有用。