虽然知道如何计算出特定问题的大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!)来推导更简单的渐近复杂度公式

好问题!

免责声明:这个答案包含虚假陈述，见下面的评论。

如果您正在使用大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这样依赖于数组大小的东西，并根据你的数据结构推理什么样的输入会导致简单的情况，什么样的输入会导致最坏的情况。

让我们从头说起。

首先，接受这样一个原则:对数据的某些简单操作可以在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运算符组合。这是我知道的唯一办法。

欲了解更多信息，请查看有关该主题的维基百科页面。

我不知道如何通过编程来解决这个问题，但人们做的第一件事是我们对算法的特定模式进行抽样，比如4n²+ 2n + 1我们有两个规则:

如果我们有一个项的和，增长率最大的项被保留，其他项被省略。 如果我们有几个因数的乘积，常数因数就省略了。

如果我们化简f(x)，其中f(x)是所做操作数量的公式，(上文解释的4n²+ 2n + 1)，我们得到大O值[在这种情况下是O(n²)]。但这必须考虑到程序中的拉格朗日插值，这可能很难实现。如果真正的大O值是O(2^n)我们可能有O(x^n)这样的东西，那么这个算法可能是不可编程的。但如果有人证明我错了，给我代码. . . .

小提示:大O符号是用来表示渐近复杂度的(也就是说，当问题的大小增长到无穷大时)，它隐藏了一个常数。

这意味着在O(n)和O(n2)的算法之间，最快的并不总是第一个算法(尽管总是存在一个值n，这样对于大小为>n的问题，第一个算法是最快的)。

注意，隐藏常数很大程度上取决于实现!

此外，在某些情况下，运行时并不是输入大小为n的确定函数。以快速排序为例:对n个元素的数组进行排序所需的时间不是一个常数，而是取决于数组的初始配置。

有不同的时间复杂度:

最坏的情况(通常是最简单的，但并不总是很有意义) 一般情况下(通常很难弄清楚…) .．.

一个很好的介绍是R. Sedgewick和P. Flajolet的《算法分析导论》。

正如你所说，过早的优化是万恶之源，(如果可能的话)在优化代码时真的应该总是使用分析。它甚至可以帮助您确定算法的复杂性。