O(N！)意味着对N个元素的所有可能排列进行处理。一个旅行推销员就是一个例子，那里有N个！一种访问节点的方法，而强力解决方案是查看每种可能排列的总成本以找到最佳排列。

• 就像O(n ^ 2)运算会做什么一样？
• 如果操作是O(n log(n))，这意味着什么呢？
• 有人要抽烟写O(x！)吗？

回答

我们可能会发现可视化它很有用：

同样，在LogY / LogX比例尺上，函数n1 / 2，n，n2都看起来像直线，而在LogY / X比例尺2n，en，10n上则是直线，而n！是线性的(看起来像n log n)。

log(n)表示对数增长。一个例子就是分而治之算法。如果我们在数组中有1000个排序的数字(例如3、10、34、244、1203 ...)，并且想要在列表中搜索一个数字(查找其位置)，则可以先检查索引500上的数字。如果它低于所需的值，则跳到750。如果它高于所需的值，则跳到250。然后重复该过程，直到找到值(和键)。每次我们跳过一半的搜索空间时，我们都可以剔除测试许多其他值的步骤，因为我们知道数字3004不能超过数字5000(请记住，这是一个有序列表)。

n log(n)则表示n * log(n)。

要了解O(n log n)，请记住log n表示n的log-base-2. 然后看一下每个部分：

当我们对集合中的每个项目进行操作时，O(n)或者多或者少是。

O(log n)是当操作数与我们将其乘以2的指数相同时，得到的项数。例如，二进制搜索必须将集合减少一半对数n次。

O(n log n)是一种组合，我们正在针对该集中的每个项目执行二进制搜索。高效的排序通常是通过对每个项目执行一个循环来进行的，并且在每个循环中进行一次良好的搜索以找到正确的位置来放置有问题的项目或者组。因此，n * log n。

Big-O表示法对代码而言，最重要的事情是，当我们将其操作的"事物"数量加倍时，它将如何扩展。这是一个具体的例子：

因此，选择快速排序为O(n log(n))与气泡排序为O(n ^ 2)。当排序10件事时，快速排序比气泡排序快3倍。但是，当排序100件商品时，速度提高了14倍！显然，选择最快的算法非常重要。当我们访问具有百万行的数据库时，这可能意味着查询在0.2秒内执行与花费数小时之间的差异。

要考虑的另一件事是，糟糕的算法是摩尔定律无法解决的一件事。例如，如果我们有一个科学的计算量为O(n ^ 3)，并且一天可以计算100件事，那么处理器速度加倍，一天就只能得到125件事。但是，将该计算取为O(n ^ 2)，我们一天就要做1000件事。

澄清：
实际上，Big-O并没有说明在相同的特定大小点上不同算法的比较性能，而是针对相同的算法在不同大小点上的比较性能：

这可能太数学了，但这是我的尝试。 (我是数学家。)

如果某物为O(f(n))，则它在n个元素上的运行时间将等于A f(n)+ B(以时钟周期或者CPU操作为单位进行衡量)。理解这些常量A和B也是关键，这些常量A和B是由特定的实现产生的。 B本质上表示操作的"固定开销"，例如，我们进行的某些预处理不依赖于集合的大小。 A代表我们实际项目处理算法的速度。

但是，关键是要使用大O表示法来确定事物的扩展程度。因此，这些常数并不重要：如果我们想弄清楚如何将项目从10扩展到10000，谁在乎常数B？同样，其他问题(请参阅下文)肯定会超过乘法常数A的权重。

所以真正的交易是f(n)。如果f根本不随n增长，例如f(n)= 1，那么我们将得到惊人的扩展---运行时间将始终为A +B。如果f随着n线性增长，即f(n)= n，则运行时间将扩展为最好的是可以预期的-如果用户等待10 ns的10个元素，他们将等待10000 ns的10000个元素(忽略加性常数)。但是，如果它像n2一样增长得更快，那就麻烦了；当我们获得更大的收藏集时，事情将会开始放慢太多。 f(n)= n log(n)通常是一个很好的折衷方案：操作不能如此简单以至于可以进行线性缩放，但是我们已经设法将其缩减，从而使其缩放效果远胜于f (n)= n2.

实际上，这里有一些很好的例子：

我喜欢don neufeld的答案，但我想我可以添加一些有关O(n log n)的信息。

Big-O       |  computations for 10 things |  computations for 100 things
----------------------------------------------------------------------
O(1)        |   1                         |     1
O(log(n))   |   3                         |     7
O(n)        |  10                         |   100
O(n log(n)) |  30                         |   700
O(n^2)      | 100                         | 10000

使用简单的分而治之策略的算法可能将是O(log n)。最简单的例子是在排序列表中查找某物。我们无需从头开始并进行扫描。我们走到中间，决定是应该向前还是向后前进，跳到最后看的位置的一半，然后重复此操作直到找到所需的项目。

如果查看quicksort或者mergesort算法，我们将看到它们都采用将要排序的列表分成两半，对每一半进行排序(递归使用同一算法)，然后将两半重新组合的方法。这种递归的分而治之策略将是O(n log n)。

如果仔细考虑一下，我们会发现quicksort对整个n个项目执行O(n)分区算法，然后对n / 2个项目进行O(n)分区两次，然后对n / 4个项目进行4次分区，等等...直到我们获得1个项的n个分区(简并)。将n除以1的次数大约为log n，每个步骤为O(n)，因此递归除法和征服为O(n log n)。 Mergesort以另一种方式构建，以1项的n个重组开始，以n项的1种重组结束，其中两个排序列表的重组为O(n)。

computations     computations       computations
Big-O       |   for 10 things |  for 100 things |  for 1000 things
----------------------------------------------------------------------
O(1)        |        1        |        1        |         1
O(log(n))   |        1        |        3        |         7
O(n)        |        1        |       10        |       100
O(n log(n)) |        1        |       33        |       664
O(n^2)      |        1        |      100        |     10000

至于编写O(n！)算法的方法，除非我们别无选择，否则我们将是吸烟者。上面给出的旅行推销员问题被认为是这样的问题之一。

大多数乔恩·本特利(Jon Bentley)的书籍(例如《编程珍珠》(Programming Pearls))都以一种非常务实的方式涵盖了此类内容。他的演讲包括对快速分类的这种分析。

尽管与该问题并不完全相关，但Knuth提出了一个有趣的想法：在高中微积分课程中教授Big-O表示法，尽管我发现这个想法很古怪。

好的，这里有一些很好的答案，但是几乎所有的答案似乎都犯了相同的错误，并且这是普遍使用的错误。

非正式地，我们写为f(n)= O(g(n))，如果不超过比例因子，并且对于所有大于某个n0的n，g(n)都大于f(n)。也就是说，f(n)的增长速度不比g(n)快，或者从上面受g(n)限制。这没有告诉我们关于f(n)增长的速度，除了保证它不比g(n)差的事实。

• O(1)：从数组中检索元素。我们确切知道它在内存中的位置，所以我们就去获取它。集合有10个项目还是10000个项目都没有关系；它仍然在索引3上，所以我们只是跳到内存中的位置3.
• O(n)：从链表中检索元素。在这里，A = 0.5，因为平均而言，在找到要查找的元素之前，我们必须先经过链表的1/2.
• O(n2)：各种"哑"排序算法。因为通常他们的策略涉及到每个元素(n)，所以我们要查看所有其他元素(因此乘以另一个n，得到n2)，然后将自己放置在正确的位置。
• O(n log(n))：各种"智能"排序算法。事实证明，我们只需要查看1010个元素的集合中的10个元素，即可相对于集合中的其他每个人智能地对自己进行排序。因为其他所有人也将查看10个元素，并且紧急行为的安排恰到好处，因此足以产生一个排序列表。
• O(n！)：一种"尝试所有内容"的算法，因为存在(与n成正比)！可能解决给定问题的n个元素的可能组合。因此，它只是循环遍历所有此类组合，尝试它们，然后在成功时停止。

一个具体的例子：n = O(2 ^ n)。我们都知道n的增长速度远小于2 ^ n，因此使我们有资格说n受到指数函数的限制。 n和2 ^ n之间有很多空间，因此这不是一个很严格的界限，但仍然是一个合理的界限。

为什么我们(计算机科学家)使用界限而不是精确的界限？因为a)边界通常更容易证明，b)它为我们提供了表达算法属性的捷径。如果我说我的新算法是O(n.log n)，这意味着在最坏的情况下，它的运行时将在n个输入上受到n.log n的限制，对于n足够大(尽管请参阅下面的评论)关于何时我可能不是最坏的情况)。

如果相反，我们想说一个函数的增长与其他函数完全一样快，我们使用theta来说明这一点(我将T(f(n)写成markdown中f(n)的\ Theta) 。 T(g(n))是由g(n)上下限制的又一捷径，它再次达到比例因子并渐近。

即f(n)= T(g(n))== f(n)= O(g(n))和g(n)= O(f(n))。在我们的示例中，我们可以看到n！= T(2 ^ n)，因为2 ^ n！= O(n)。

为什么要为此担心？因为在问题中我们写道："有人要抽烟写O(x！)吗？"答案是否定的，因为基本上我们编写的所有内容都将受到阶乘函数的限制。 quicksort的运行时间为O(n！)，这不是一个严格的界限。

这里还有另一个微妙的方面。通常，当我们使用O(g(n))表示法时，是在讨论最坏情况的输入，因此我们在做复合语句：在最坏情况下，运行时间不会比使用g(n)的算法更糟糕。 )步骤，再次进行模缩放，并获得足够大的n。但是有时候我们想谈一谈平均甚至最佳情况下的运行时间。

像以前一样，Villailla quicksort是一个很好的例子。在最坏的情况下为T(n ^ 2)(实际上至少要执行n ^ 2步，但不会多得多)，但在一般情况下为T(n.log n)，也就是说，期望的数量为T(n ^ log n)。步长与n.log n成正比。在最好的情况下，它也是T(n.log n)，但是我们可以通过例如检查数组是否已经排序的方式来改进它，在这种情况下，最好的情况下运行时间是T(n)。

这与我们关于这些界限的实际实现的问题有什么关系？好吧，不幸的是，O()符号隐藏了现实世界中必须处理的常量。因此，尽管我们可以说，例如，对于T(n ^ 2)运算，我们必须访问每个可能的元素对，但是我们不知道我们必须访问它们多少次(除了这不是函数的函数) n)。因此，我们可能不得不每对访问10次或者10 ^ 10次，并且T(n ^ 2)语句没有区别。低阶函数也被隐藏了，因为n ^ 2 + 100n = T(n ^ 2)，所以我们可能必须访问每对元素一次，每个元素访问100次。 O()表示法的思想是，对于足够大的n，这根本不重要，因为n ^ 2变得比100n大得多，以至于我们甚至都没有注意到100n对运行时间的影响。但是，我们经常处理"足够小"的n，以使恒定因子等产生真正的显着差异。

例如，快速排序(平均成本T(n.log n))和堆排序(平均成本T(n.log n))都是具有相同平均成本的排序算法，但快速排序通常比堆排序要快得多。这是因为堆排序每个元素比快速排序进行更多的比较。

这并不是说O()符号没有用，只是不精确。对于小n来说，这是一个非常钝的工具。

(作为本论文的最后注解，请记住，O()符号仅描述了任何功能的增长，它不一定是时间，它可能是内存，分布式系统中交换的消息，或者是并行算法。)

只是为了回应我上面的帖子中的几条评论：

Domenic我在这个网站上，我在乎。不是为了学究，而是因为我们作为程序员通常关心精度。错误地使用O()表示法(有些人在这里做过的风格)使其变得毫无意义。我们可以说，根据此处使用的约定，某些事物需要O(n ^ 2)的n ^ 2个时间单位。使用O()不会增加任何内容。我在谈论的不仅仅是普通用法和数学精度之间的微小差异，而是有意义与否之间的区别。

我知道很多很多优秀的程序员都在精确地使用这些术语。说"哦，我们是程序员，所以我们不在乎"会使整个企业便宜。

onebyone好吧，虽然我同意你的意思，但不是真的。任意大的n都不是O(1)，这是O()的定义。它只是表明O()对于有界的n的适用性有限，在这里我们宁愿实际上谈论所采取的步骤数，而不是该数目的界数。

don.neufeld的答案非常好，但我可能会分两部分进行解释：首先，大多数算法都属于O()的粗略层次结构。然后，我们可以查看其中的每一个，以得出该时间复杂度的典型算法的功能草图。

出于实际目的，似乎唯一重要的O()是：

就是这样。它们之间有很多其他可能性(或者大于O(2 ^ n))，但是它们在实践中并不经常发生，并且在质量上与其中一种并没有太大不同。三次算法已经有点麻烦了；我之所以只包括它们，是因为我经常碰到它们，足以值得一提(例如矩阵乘法)。

这些类的算法实际上发生了什么？好吧，我认为我们有一个良好的开端，尽管有许多示例不适合这些特征。但对于以上内容，我想说的通常是这样的：

这些都不是严格的。尤其是非线性时间算法(O(n))：我可以举出许多示例，其中我们必须查看所有输入，然后查看一半，然后再查看一半，等等。反之亦然-我们将输入对折叠在一起，然后递归输出。这些不符合上面的描述，因为我们不会一次查看每个输入，但仍会在线性时间内显示出来。尽管如此，在99.2％的时间中，线性时间仍意味着每个输入一次查看。

我的思考方式是，我们要清理一个由邪恶的恶棍V挑出N所引起的问题，并且我们必须估算出当他增加N时解决问题所需的时间。

O(1)->增加N真的没有任何区别

O(log(N))->每当V翻倍N时，我们就必须花费额外的时间T才能完成任务。 V再次将N翻倍，我们花了相同的金额。

O(N)->每次V使N翻倍，我们花费的时间就会增加一倍。

O(N ^ 2)->每当V将N翻倍时，我们要花费4倍的时间。 (这不公平！！！)

O(N log(N))->每次V使N翻倍时，我们花费的时间是原来的两倍，多一点。

• O(1)"恒定时间"-所需时间与输入大小无关。作为一个粗略的分类，我将在此处包括哈希查找和联合查找之类的算法，即使它们实际上都不是O(1)。
• 我们输入的整个图形结构是相关的
• O(2 ^ n)-我们需要考虑输入的每个可能子集。
• 有人要抽烟写O(x！)吗？
• 大八岁的孩子？
• 解决方案
• 回答

这些是算法的界限；计算机科学家想描述大的N值要花多长时间。(当我们考虑密码学中使用的数字时，这一点很重要-如果计算机的速度提高了10倍，我们又需要多少位必须使用以确保仍然需要100年才能破解加密，而不仅仅是1年？)

如果某些界限对所涉人员有所影响，则可能会有一些怪异的表述。我在Knuth的《计算机编程艺术》中的某些算法中见过O(N log(N)log(log(N)))之类的东西。 (不记得哪一个离我的头顶了)

• 回答
• 回答
• 回答
• 回答
• 回答

由于某种原因尚未涉及的一件事：

当我们看到算法具有O(2 ^ n)或者O(n ^ 3)或者其他讨厌的值时，通常意味着我们将不得不接受不完美的问题答案才能获得可接受的性能。

处理优化问题时，通常会冒出这样的正确解决方案。在合理的时间范围内提供的几乎正确的答案要比机器腐烂很久以后提供的正确答案要好。

考虑一下国际象棋：我不知道确切的解决方案是什么，但是可能是O(n ^ 50)甚至更糟。从理论上讲，任何计算机都不可能真正计算出正确的答案-即使我们将宇宙中的每个粒子都用作在整个宇宙生命中以最短的时间执行操作的计算元素，我们仍然还有很多零。 (量子计算机是否可以解决它是另一回事。)

可以将其视为垂直堆叠乐高积木(n)并跳过它们。

O(1)表示在每一步中我们什么都不做。高度保持不变。

O(n)表示在每一步中，我们堆叠c个块，其中c1是一个常数。

O(n ^ 2)表示在每一步中，我们堆叠c2 x n个块，其中c2是一个常数，而n是堆叠的块数。

O(nlogn)表示在每个步骤中，堆叠c3 x n x log n个块，其中c3是常数，n是堆叠的块数。

我想问更多关于这对我的代码意味着什么。我从数学上理解这些概念，我很难理解它们在概念上的含义。例如，如果要对一个数据结构执行O(1)操作，我知道它必须执行的操作量不会增加，因为有更多的项。 O(n)操作意味着我们将对每个元素执行一组操作。有人可以在这里填补空白吗？

告诉我们八岁的log(n)意味着我们必须将长度n切短两次的次数才能减小到n = 1：p

O(n log n)通常在排序
O(n ^ 2)通常在比较所有元素对

不，只需使用Prolog。如果我们在Prolog中编写排序算法，只是描述每个元素应该大于前一个元素，然后让backtracking为我们进行排序，则将为O(x！)。也称为"排列排序"。

Big-O背后的"直觉"

其中许多很容易通过非编程方式(例如混洗卡)进行演示。

想象一下x上两个函数之间的"竞争"，因为x接近无穷大：f(x)和g(x)。

现在，如果从某个点开始(某个x)，一个函数总是比另一个函数具有更高的值，那么我们将此函数称为比另一个函数"更快"。

因此，例如，如果对于每一个x> 100，我们都看到f(x)> g(x)，则f(x)比g(x)"更快"。

在这种情况下，我们说g(x)= O(f(x))。 f(x)构成了g(x)的某种"限速"，因为最终它通过了它并永远留下来。

这不完全是big-O表示法的定义，它还指出，对于某个常数C，f(x)仅必须大于C * g(x)(这是另一种说法，我们不能通过乘以常数f(x)来帮助g(x)赢得比赛，最终总会获胜)。形式定义也使用绝对值。但是我希望我能使它直观。

通过遍历整个牌组以找到黑桃A来对一副扑克牌进行排序，然后遍历整个牌组以找到黑桃A中的2张，依此类推，如果牌组已经向后排序，那将是最坏的情况n ^ 2. 我们看了全部52张牌52次。

假设我们有一台可以解决一定大小问题的计算机。现在想象一下，我们可以将性能提高一倍。每增加一倍，我们可以解决多大的问题？

如果我们可以解决两倍大小的问题，那就是O(n)。

通常，真正糟糕的算法不一定是故意的，它们通常是对其他事物的滥用，例如在其他在同一集合上线性重复的方法中调用线性方法。

• 回答

如果我们有一个不是一个乘数的乘数，那就是多项式复杂度。例如，如果每次加倍允许我们将问题大小增加大约40％，则为O(n ^ 2)，而大约30％将为O(n ^ 3)。

不，O(n)算法并不意味着它将对每个元素执行一个运算。 Big-O表示法为我们提供了一种与实际机器无关地讨论算法"速度"的方式。

如果我们仅增加问题的大小，那将是指数级或者更糟。例如，如果每个加倍意味着我们可以解决更大的问题1，那么它就是O(2 ^ n)。 (这就是为什么使用合理大小的密钥实际上无法强行使用密码密钥的原因：128位密钥所需的处理量是64位密钥的16倍，即大约五分之一。)

我向非技术朋友描述的方式是这样的：

考虑多位数加法。好老式的铅笔和纸。我们7-8岁时所学的那种。给定两个三位数或者四位数的数字，我们可以很容易地找出它们的总和。

如果我给我们两个100位数字，然后问他们加起来的数字，即使我们必须使用铅笔和纸，弄清楚它也是非常简单的。一个聪明的孩子可以在短短几分钟内完成这样的添加。这仅需要大约100次操作。

现在，考虑多位数乘法。我们可能在8或者9岁时就知道了。我们(希望)进行了大量重复的练习，以了解其背后的机制。

现在，假设我给了我们同样的两个100位数字，并告诉我们将它们相乘。这将是一项非常艰巨的任务，这将花费我们数小时的时间，而且我们很可能不会犯错误。原因是(此版本的)乘法是O(n ^ 2);底数中的每个数字必须与顶数中的每个数字相乘，总共需要进行大约n ^ 2次运算。如果是100位数字，那就是10,000个乘法。

O(n)表示算法将花费的时间随着输入的增加而线性增加。 O(n ^ 2)表示算法花费的时间随着输入平方的增加而增加。依此类推。

还记得乌龟和野兔(乌龟和兔子)的寓言吗？

从长远来看，乌龟会胜出，但从短期来看，野兔会胜出。

就像O(logN)(乌龟)vs.O(N)(野兔)。

如果两种方法的big-O有所不同，那么其中一个将获胜的级别为N，但是big-O并没有说明N的大小。

一种思考的方式是：

我尝试通过在C＃中给出简单的代码示例来进行解释。

对于List <int>数字=新的List <int> {1,2,3,4,5,6,7,12,543,7};

O(1)看起来像

O(n)看起来像

O(n log(n))看起来像

O(N ^ 2)意味着对于每个元素，我们正在与其他所有元素一起做某事，例如比较它们。冒泡排序就是一个例子。

O(n ^ 2)看起来像

O(n！)看起来很累，想出任何简单的方法。
但我希望我们能理解一般点？

O(N log N)意味着对于每个元素，我们所做的事情仅需要查看元素的logN。这通常是因为我们了解一些有关元素的知识，这些元素使我们可以做出有效的选择。最有效的排序就是这种示例，例如合并排序。

return numbers.First();

int result = 0;
foreach (int num in numbers)
{
    result += num;
}
return result;

int result = 0;
foreach (int num in numbers)
{
    int index = numbers.length - 1;
    while (index > 1)
    {
        // yeah, stupid, but couldn't come up with something more useful :-(
        result += numbers[index];
        index /= 2;
    }
}
return result;

int result = 0;
foreach (int outerNum in numbers)
{
    foreach (int innerNum in numbers)
    {
        result += outerNum * innerNum;
    }
}
return result;