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

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

让我们从头说起。

首先，接受这样一个原则:对数据的某些简单操作可以在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²)运行时间。

一个更实际的例子。

我从信息的角度来考虑。任何问题都包括学习一定数量的比特。

你的基本工具是决策点及其熵的概念。一个决策点的熵是它会给你的平均信息。例如，如果一个程序包含一个有两个分支的决策点，它的熵是每个分支的概率乘以该分支的逆概率的log2的和。这就是你从执行决策中学到的东西。

例如，一个if语句有两个分支，都是等可能的，其熵为1/2 * log(2/1) + 1/2 * log(2/1) = 1/2 * 1 + 1/2 * 1 = 1。所以它的熵是1比特。

假设您正在搜索一个包含N个条目的表，例如N=1024。这是一个10位问题，因为log(1024) = 10位。所以如果你可以用if语句搜索结果的可能性相等，它应该需要10个决定。

这就是二分搜索的结果。

假设你在做线性搜索。您查看第一个元素并询问它是否是您想要的元素。是的概率是1/1024，不是的概率是1023/1024。该决策的熵为1/1024*log(1024/1) + 1023/1024 *log(1024/1023) = 1/1024* 10 + 1023/1024 * about 0 =约0.01 bit。你学得太少了!第二个决定也好不到哪里去。这就是为什么线性搜索这么慢。事实上，你需要学习的比特数是指数级的。

假设你在做索引。假设表被预先排序到许多箱子中，并且您使用键中的所有位中的一些位直接索引到表项。如果有1024个箱子，熵为1/1024 * log(1024) + 1/1024 * log(1024) +…对于所有1024个可能的结果。这是1/1024 * 10乘以1024个结果，或者对一个索引操作来说是10比特的熵。这就是为什么索引搜索是快速的。

现在想想排序。你有N个项目，你有一个列表。对于每个项目，您必须搜索项目在列表中的位置，然后将其添加到列表中。排序大约需要N倍于底层搜索的步数。

基于二元决策的排序结果都是等概率的都需要O(N log N)步。基于索引搜索的O(N)排序算法是可行的。

我发现几乎所有的算法性能问题都可以用这种方式来看待。

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

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

虽然知道如何计算出特定问题的大O时间是有用的，但了解一些一般情况可以在很大程度上帮助您在算法中做出决策。

以下是一些最常见的案例，摘自http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:

O(1) -确定一个数字是偶数还是奇数;使用常量大小的查找表或哈希表

O(logn) -用二分搜索在排序数组中查找一个项

O(n) -在未排序的列表中查找一个项;两个n位数相加

O(n2) -用一个简单的算法乘以两个n位数字;添加两个n×n矩阵;冒泡排序或插入排序

O(n3) -用简单的算法乘以两个n×n矩阵

O(cn) -使用动态规划找到旅行商问题的(精确)解;使用蛮力判断两个逻辑语句是否等效

O(n!) -通过暴力搜索解决旅行推销员问题

O(nn) -通常用来代替O(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²)一样，没有格式。