让我们从头说起。

首先，接受这样一个原则:对数据的某些简单操作可以在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，那么您正在谈论的是最坏的情况(后面将详细介绍它的含义)。此外，在平均情况下有大写的theta，在最佳情况下有大的omega。

你可以在这个网站上找到大O的正式定义:https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n))表示存在正常数c和k，使得当n≥k时0≤f(n)≤cg(n)。对于函数f, c和k的值必须是固定的，且不依赖于n。

好的，那么我们所说的"最佳情况"和"最坏情况"是什么意思呢?

这一点可以通过例子得到最清楚的说明。例如，如果我们使用线性搜索在一个排序数组中查找一个数字，那么最坏的情况是我们决定搜索数组的最后一个元素，因为这将花费与数组中有多少项一样多的步骤。最好的情况是当我们搜索第一个元素时，因为我们将在第一次检查之后完成。

The point of all these adjective-case complexities is that we're looking for a way to graph the amount of time a hypothetical program runs to completion in terms of the size of particular variables. However for many algorithms you can argue that there is not a single time for a particular size of input. Notice that this contradicts with the fundamental requirement of a function, any input should have no more than one output. So we come up with multiple functions to describe an algorithm's complexity. Now, even though searching an array of size n may take varying amounts of time depending on what you're looking for in the array and depending proportionally to n, we can create an informative description of the algorithm using best-case, average-case, and worst-case classes.

抱歉，这是如此糟糕的写作和缺乏太多的技术信息。但希望这能让时间复杂度类更容易理解。一旦你熟悉了这些，你就可以很简单地解析你的程序，寻找像for-loops这样依赖于数组大小的东西，并根据你的数据结构推理什么样的输入会导致简单的情况，什么样的输入会导致最坏的情况。

我认为，一般来说用处不大，但为了完整起见，还有一个Big Omega Ω，它定义了算法复杂度的下界，还有一个Big Theta Θ，它同时定义了上界和下界。

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

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

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

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

虽然知道如何计算出特定问题的大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²)一样，没有格式。