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

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

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

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。

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

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

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

为什么要去掉两个2 ?

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

考虑2N和2这两项。

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

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

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

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

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

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

所以2N变成了N。

其他答案集中在大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万美元的奖励。

从这里开始-算法的时间复杂度介绍

1. 简介

在计算机科学中，算法的时间复杂度将算法运行所需的时间量化为表示输入的字符串长度的函数。

2. 大O符号

算法的时间复杂度通常用大O符号表示，其中不包括系数和低阶项。当以这种方式表示时，时间复杂度被称为渐近描述，即当输入大小趋于无穷大时。

例如，如果一个算法对所有大小为n的输入所需要的时间最多为5n3 + 3n，则渐近时间复杂度为O(n3)。稍后再详细介绍。

再举几个例子:

1 = O（n） n = O（n2） log（n） = O（n） 2 n + 1 = O（n）

3.O(1)常数时间:

不管输入大小如何，如果一个算法需要相同的时间，我们就说它在常数时间内运行。

例子:

数组:访问任意元素 固定大小的堆栈:push和pop方法 固定大小的队列:入队列和出队列方法

4. O(n)线性时间

如果一个算法的时间执行与输入大小成正比，即时间随着输入大小的增加而线性增长，则该算法被称为在线性时间内运行。

考虑下面的例子。下面我线性搜索一个元素，它的时间复杂度是O(n)。

int find = 66;
var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 };
for (int i = 0; i < numbers.Length - 1; i++)
{
    if(find == numbers[i])
    {
        return;
    }
}

更多的例子:

数组:线性搜索，遍历，查找最小值等 ArrayList:包含方法 Queue:包含方法

5. O(log n)对数时间:

如果一个算法的执行时间与输入大小的对数成正比，则该算法在对数时间内运行。

示例:二分搜索

回想一下“二十个问题”游戏——任务是在一段时间内猜测一个隐藏数字的值。每次你猜的时候，都会被告知你猜的是太高还是太低。二十题游戏暗示了一种策略，使用你的猜测数字来减半间隔大小。这是一个被称为二分搜索的一般问题解决方法的例子。

6. O(n2)二次时间

如果一个算法的执行时间与输入大小的平方成正比，我们就说它在二次时间内运行。

例子:

冒泡排序 选择排序 插入排序

7. 一些有用的链接

大0误解 算法复杂度的确定 大O小抄

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