简单地说，时间复杂度是一种总结算法的操作数量或运行时间如何随着输入大小的增加而增长的方式。

就像生活中的大多数事情一样，鸡尾酒会可以帮助我们理解。

O(N)

当你到达派对时，你必须和每个人握手(每件事都要做一次操作)。随着出席人数N的增加，你与每个人握手的时间/工作时间也随着O(N)的增加而增加。

为什么是O(N)而不是cN?

与人握手所用的时间各不相同。你可以把它平均出来，用常数c来表示。但这里的基本操作——和每个人握手——总是与O(N)成正比，不管c是多少。当我们讨论是否应该参加鸡尾酒会时，我们通常更感兴趣的是我们必须与每个人见面，而不是那些会面的细节。

O (N ^ 2)

鸡尾酒会的主人想让你玩一个愚蠢的游戏，让每个人都遇见其他人。因此，你必须会见N-1个人，因为下一个人已经见过你，他们必须会见N-2个人，以此类推。这个级数的和是x^2/2+x/2。随着参与者人数的增加，x^2项很快就变大了，所以我们就把其他的都丢掉了。

O (N ^ 3)

你必须和其他人见面，在每次会议期间，你必须谈论房间里的其他人。

O(1)

主持人想宣布一件事。他们敲着酒杯大声说话。每个人都能听到。事实证明，不管有多少参与者，这个操作总是花费相同的时间。

O（对数 N）

主人已经把每个人按字母顺序排列在桌子上。丹在哪里?你推断他一定在亚当和曼迪之间(当然不是在曼迪和扎克之间!)。鉴于此，他在乔治和曼迪之间吗?不。他肯定在亚当和弗雷德之间，在辛迪和弗雷德之间。等等……我们可以有效地定位丹，只需要看一半的集合，然后再看一半的集合。最终，我们观察O(log_2 N)个个体。

O(nlogn)

您可以使用上面的算法找到在桌子旁的位置。如果有很多人来到这张桌子前，一次一个，所有人都这样做，这将花费O(nlog N)个时间。结果证明，这是对必须进行比较的项目集合进行排序所需的时间。

最好/最坏情况

你到达了派对，需要找到伊尼戈——需要多长时间?这取决于你什么时候到。如果每个人都在周围转悠，你就遇到了最坏的情况:将花费O(N)时间。然而，如果每个人都坐在桌子旁，只需要O(log N)时间。或者你可以利用主持人的酒杯呐喊能力，这样只需要O(1)时间。

假设主机不可用，我们可以说inigo查找算法的下界为O(log N)，上界为O(N)，这取决于您到达时聚会的状态。

空间与通信

同样的想法也可以应用于理解算法如何使用空间或通信。

Knuth写了一篇关于前者的好论文，题为《歌曲的复杂性》。

定理2:存在复杂度为O(1)的任意长歌曲。 证据:(由于凯西和阳光乐队)。考虑一下Sk用(15)定义的歌曲，但是用

V_k = 'That's the way,' U 'I like it, ' U
U   = 'uh huh,' 'uh huh'

对于所有的k。

其他答案集中在大o符号和实际例子上。我想从理论的角度来回答这个问题。下面的解释必然缺乏细节;Michael Sipser的《计算理论导论》是学习计算复杂性理论的一个很好的来源。

图灵机

研究计算问题的最广泛的模型是图灵机。图灵机有一个一维的纸带，上面有符号，用作存储设备。它有一个磁带头，用来从磁带中读写。它有一个决定机器行为的转换表，这是一个在机器创建时决定的固定硬件组件。图灵机在离散时间步长下工作，如下所示:

它能读出胶带下面的符号。 根据符号及其内部状态(只能取有限个值)的不同，它从转换表中读取三个值s、σ和X，其中s是内部状态，σ是符号，X是左或右。

它的内部状态变成了s。

它将读取的符号更改为σ。

它将磁带头按照X的方向移动一步。

图灵机是强大的计算模型。它们能做你的数字计算机能做的一切。它们是在现代数字计算机出现之前由理论计算机科学之父和数学家艾伦·图灵提出的。

时间复杂度

It is hard to define the time complexity of a single problem like "Does white have a winning strategy in chess?" because there is a machine which runs for a single step giving the correct answer: Either the machine which says directly 'No' or directly 'Yes'. To make it work we instead define the time complexity of a family of problems L each of which has a size, usually the length of the problem description. Then we take a Turing machine M which correctly solves every problem in that family. When M is given a problem of this family of size n, it solves it in finitely many steps. Let us call f(n) the longest possible time it takes M to solve problems of size n. Then we say that the time complexity of L is O(f(n)), which means that there is a Turing machine which will solve an instance of it of size n in at most C.f(n) time where C is a constant independent of n.

它不是依赖于机器吗?数字计算机能做得更快吗?

Yes! Some problems can be solved faster by other models of computation, for example two tape Turing machines solve some problems faster than those with a single tape. This is why theoreticians prefer to use robust complexity classes such as NL, P, NP, PSPACE, EXPTIME, etc. For example, P is the class of decision problems whose time complexity is O(p(n)) where p is a polynomial. The class P do not change even if you add ten thousand tapes to your Turing machine, or use other types of theoretical models such as random access machines.

理论与实践的差异

通常假设整数加法的时间复杂度为O(1)。这种假设在实践中是有意义的，因为计算机使用固定数量的位来存储许多应用程序的数字。理论上没有理由假设这样的事情，所以加法的时间复杂度是O(k)其中k是表示整数所需的比特数。

寻找一类问题的时间复杂度

显示问题时间复杂度的最直接方法是构造一个图灵机，它能在O(f(n))时间内解决问题。为复杂问题创建图灵机并非易事;人们需要熟悉它们。图灵机的转换表很少给出，它是高层次的描述。随着人们对机器的熟悉，就更容易看到机器需要多长时间才能停下来。

说明一个问题不是O(f(n))时间复杂度是另一回事……尽管有一些像时间层次定理这样的结果，但这里还有很多悬而未决的问题。例如，NP中的问题是否在P中，即是否可在多项式时间内解决，是数学千年大奖中的七个问题之一，解决者将获得100万美元的奖励。

如何计算算法的时间复杂度

你把它将执行的机器指令数量作为输入大小的函数相加，然后将表达式简化为最大(当N非常大时)项，并可以包括任何简化的常数因子。

例如，让我们看看如何简化2N + 2个机器指令，将其描述为O(N)。

为什么要去掉两个2 ?

我们感兴趣的是N变大时算法的性能。

考虑2N和2这两项。

当N变大时，这两项的相对影响是什么?假设N是一百万。

第一项是200万，第二项只有2。

因此，对于大N，我们只保留最大的项。

现在我们从2N + 2到2N。

传统上，我们只对常数因素下的性能感兴趣。

这意味着当N很大时，我们并不关心性能差异是否有常数倍数。2N的单位一开始就没有明确定义。所以我们可以乘或除一个常数因子得到最简单的表达式。

所以2N变成了N。

这是一篇很好的文章:算法的时间复杂度

下面的答案是从上面复制的(以防优秀的链接崩溃)

计算时间复杂度最常用的度量是大O符号。这样就去掉了所有的常数因子，这样当N趋于无穷时，运行时间就可以相对于N进行估计。一般来说，你可以这样想:

statement;

是恒定的。语句的运行时间不会随着N的变化而改变。

for ( i = 0; i < N; i++ )
     statement;

是线性的。循环的运行时间与N成正比，当N加倍时，运行时间也加倍。

for ( i = 0; i < N; i++ ) {
  for ( j = 0; j < N; j++ )
    statement;
}

是二次。两个循环的运行时间与N的平方成正比，当N翻倍时，运行时间增加N * N。

while ( low <= high ) {
  mid = ( low + high ) / 2;
  if ( target < list[mid] )
    high = mid - 1;
  else if ( target > list[mid] )
    low = mid + 1;
  else break;
}

对数。算法的运行时间与N能被2除的次数成正比。这是因为算法在每次迭代时都将工作区域分成两半。

void quicksort (int list[], int left, int right)
{
  int pivot = partition (list, left, right);
  quicksort(list, left, pivot - 1);
  quicksort(list, pivot + 1, right);
}

为N * log (N)。运行时间由N个对数循环(迭代或递归)组成，因此该算法是线性和对数的结合。

一般来说，对一维中的每一项都做某事是线性的，对二维中的每一项都做某事是二次的，将工作区域一分为二是对数的。还有其他的大O测量方法，如立方、指数和平方根，但它们并不常见。大O符号被描述为O(<类型>)，其中<类型>是度量。快速排序算法可以描述为O (N * log(N))。

请注意，所有这些都没有考虑最佳、平均和最坏的情况。每个都有自己的大O符号。还要注意，这是一个非常简单的解释。大O是最常见的，但它也更复杂。还有其他的符号，比如大的，小的o和大的。在算法分析课程之外，你可能不会遇到它们。；）

O(n)是大O符号，用于表示算法的时间复杂度。当你把一个算法的执行次数加起来时，你会得到一个像2N+2这样的结果。在这个表达式中，N是主导项(N的值增加或减少对表达式影响最大的项)。O(N)是时间复杂度N是主要项。

例子

For i = 1 to n;
  j = 0;
while(j <= n);
  j = j + 1;

这里内层循环的总执行次数为n+1，外层循环的总执行次数为n(n+1)/2，因此整个算法的总执行次数为n+1 + n(n+1/2) = (n2 + 3n)/2。 这里n²是主导项所以这个算法的时间复杂度是O(n2)

对于有数学头脑的人来说:主定理是研究复杂性时另一个有用的东西。