我更喜欢尽可能少的正式定义和简单的数学。

快速注意，这几乎肯定会混淆Big O 符号 （这是一个上限）与 Theta 符号（这是一个双边界限）。根据我的经验，这实际上是非学术环境中的典型讨论。对所引起的任何混乱道歉。

使用此图可以显示 Big O 复杂度：

我可以为 Big-O 表示法给出的最简单的定义是：

Big-O 表示法是算法复杂性的相对表示。

在这句话中有一些重要且刻意选择的词：

• 亲戚：你只能比较苹果和苹果。您无法将算法与算术乘法进行比较，而是对整数列表进行排序。但是比较两个算法进行算术运算（一次乘法，一次加法）会告诉你一些有意义的东西;
• 表示： Big-O（最简单的形式）减少了算法与单个变量之间的比较。该变量基于观察或假设来选择。例如，通常基于比较操作来比较排序算法（比较两个节点以确定它们的相对排序）。这假设比较昂贵。但是，如果比较便宜但交换费用昂贵呢？它改变了比较; 和
• 复杂性：如果需要一秒钟才能对 10,000 个元素进行排序，那么我需要多长时间才能排序一百万个元素？在这种情况下，复杂性是对其他事物的相对衡量。

当你读完其余部分后，回过头来重读上面的内容。

我能想到的 Big-O 最好的例子就是做算术。取两个数字（123456 和 789012）。我们在学校学到的基本算术运算是：

• 加成;
• 减法;
• 乘法; 和
• 师。

这些都是操作或问题。解决这些问题的方法称为算法 。

增加是最简单的。您将数字向上排列（向右）并在列中添加数字，在结果中写入该添加的最后一个数字。该数字的 “十” 部分将转移到下一列。

让我们假设添加这些数字是该算法中最昂贵的操作。按理说，要将这两个数字加在一起，我们必须将 6 位数加在一起（并且可能带有 7 位数）。如果我们将两个 100 位数字加在一起，我们必须做 100 次加法。如果我们添加两个 10,000 位数字，我们必须添加 10,000 个。

看模式？ 复杂性 （作为操作的数量）与较大数字中的数字n的数量成正比。我们称之为O（n）或线性复杂度 。

减法是类似的（除了你可能需要借用而不是随身携带）。

乘法是不同的。你将数字排成一行，取下面数字中的第一个数字，然后依次将它与顶部数字中的每个数字相乘，依此类推。因此，要将两个 6 位数相乘，我们必须进行 36 次乘法运算。我们可能需要多做 10 或 11 列添加才能获得最终结果。

如果我们有两个 100 位数字，我们需要进行 10,000 次乘法和 200 次加法。对于两百万个数字，我们需要进行一万亿（10 ¹² ）次乘法和两百万次加法。

当算法按 n 平方缩放时，这是O（n ² ）或二次复杂度 。这是介绍另一个重要概念的好时机：

我们只关心复杂性中最重要的部分。

精明的人可能已经意识到我们可以将操作次数表示为：n ² + 2n。但正如你从我们的例子中看到的那样，每个数字有两个数字，第二个词（2n）变得微不足道（占该阶段总操作的 0.0002％）。

人们可以注意到我们已经假设了最糟糕的情况。如果其中一个是 4 位数而另一个是 6 位数，则乘以 6 位数字，那么我们只有 24 次乘法。我们仍然计算'n' 的最坏情况，即当两者都是 6 位数时。因此，Big-O 表示法是关于算法的最坏情况

电话簿

我能想到的下一个最好的例子是电话簿，通常称为白页或类似的，但它会因国家而异。但我说的是那个按姓氏列出人名，然后是姓名首字母或名字，可能是地址，然后是电话号码的人。

现在，如果您指示计算机在包含 1,000,000 个名字的电话簿中查找 “John Smith” 的电话号码，您会怎么做？忽略一个事实，你可以猜到 S 的开始有多远（让我们假设你不能），你会做什么？

一个典型的实现可能是开到中间，拿 50 万^个 ，并把它比作 “史密斯”。如果恰好是 “史密斯，约翰”，我们真的很幸运。更有可能的是，“约翰史密斯” 将在该名称之前或之后。如果是在我们之后，我们将电话簿的后半部分分成两半并重复。如果是在那之前，我们将电话簿的前半部分分成两半并重复。等等。

这称为二进制搜索 ，无论您是否意识到，它每天都会在编程中使用。

因此，如果您想在一百万个名字的电话簿中找到一个名字，您最多可以通过这样做 20 次来找到任何名称。在比较搜索算法时，我们认为这种比较是我们的'n'。

• 对于 3 个名字的电话簿，它需要进行 2 次比较（最多）。
• 对于 7 最多需要 3 个。
• 15 岁需要 4 个。
• ...
• 1,000,000 需要 20。

那是惊人的好不是吗？

在 Big-O 术语中，这是O（log n）或对数复杂度 。现在，所讨论的对数可以是 ln（基数 e），log ₁₀ ，log ₂或其他一些基数。无论如何它仍然是 O（log n）就像 O（2n ² ）和 O（100n ² ）仍然都是 O（n ² ）。

在这一点上值得解释的是 Big O 可用于通过算法确定三种情况：

• 最佳案例：在电话簿搜索中，最好的情况是我们在一次比较中找到了名称。这是O（1）或不变的复杂性 ;
• 预期案例：如上所述，这是 O（log n）; 和
• 最坏情况：这也是 O（log n）。

通常我们不关心最好的情况。我们对预期和最坏的情况感兴趣。有时这些中的一个或另一个将更重要。

回到电话簿。

如果您有电话号码并想要找到姓名怎么办？警方有一本反向电话簿，但公众拒绝接受此类查询。或者是他们？从技术上讲，您可以在普通电话簿中反向查找数字。怎么样？

您从名字开始并比较数字。如果它是一场比赛，那么很棒，如果没有，你继续前进。你必须这样做，因为电话簿是无序的 （无论如何通过电话号码）。

所以要给出一个给出电话号码的名字（反向查询）：

• 最佳案例： O（1）;
• 预期案例： O（n）（500,000）; 和
• 最坏情况： O（n）（1,000,000）。

旅行推销员

这是计算机科学中一个非常着名的问题，值得一提。在这个问题上你有 N 个城镇。这些城镇中的每一个都通过一定距离的道路与一个或多个其他城镇相连。旅行推销员的问题是找到访问每个城镇的最短旅行。

听起来很简单？再想想。

如果您有 3 个城镇 A，B 和 C，所有城市之间都有道路，那么您可以去：

• A→B→C
• A→C→B
• B→C→A
• B→A→C
• C→A→B
• C→B→A

实际上还不到那个，因为其中一些是等价的（例如，A→B→C 和 C→B→A 是等价的，因为它们使用相同的道路，正好相反）。

实际上有 3 种可能性。

• 把它带到 4 个城镇，你有（iirc）12 种可能性。
• 5 岁就是 60 岁。
• 6 变为 360。

这是称为阶乘的数学运算的函数。基本上：

• 5！ = 5×4×3×2×1 = 120
• 6！ = 6×5×4×3×2×1 = 720
• 7！ = 7×6×5×4×3×2×1 = 5040
• ...
• 25！ = 25×24×...×2×1 = 15,511,210,043,330,985,984,000,000
• ...
• 50！ = 50×49×...×2×1 = 3.04140932×10 ⁶⁴

因此，旅行商问题的大 O 是O（n！）或阶乘或组合复杂性 。

当你到达 200 个城镇时，宇宙中没有足够的时间来解决传统计算机的问题。

需要考虑的事情。

多项式时间

我想要快速提及的另一点是，任何具有O（n ^a ）复杂度的算法都被认为具有多项式复杂性或者在多项式时间内是可解的。

O（n），O（n ² ）等都是多项式时间。有些问题在多项式时间内无法解决。因此，世界上使用了某些东西。公钥加密是一个很好的例子。在计算上很难找到两个非常大的素数因子。如果不是，我们就无法使用我们使用的公钥系统。

无论如何，这就是我对 Big O（修订版）的解释（希望是简单的英语）。

它显示了算法如何扩展。

O（n ² ） ：称为二次复杂度

• 1 项：1 秒
• 10 项：100 秒
• 100 项：10000 秒

请注意，项目数量增加了 10 倍，但时间增加了 10 倍² 。基本上，n = 10，因此 O（n ² ）给出了比例因子 n ² ，即 10 ² 。

O（n） ：称为线性复杂度

• 1 项：1 秒
• 10 项：10 秒
• 100 项：100 秒

这次项目数量增加了 10 倍，时间也增加了 10 倍。 n = 10，所以 O（n）的比例因子是 10。

O（1） ：称为常数复杂度

• 1 项：1 秒
• 10 项：1 秒
• 100 项：1 秒

项目数仍然增加 10 倍，但 O（1）的比例因子始终为 1。

O（log n） ：称为对数复杂度

• 1 项：1 秒
• 10 项：2 秒
• 100 项：3 秒
• 1000 项：4 秒
• 10000 项：5 秒

计算次数仅增加输入值的对数。因此，在这种情况下，假设每次计算需要 1 秒，输入n的日志是所需的时间，因此log n 。

这就是它的要点。他们减少了数学，所以它可能不是 n ²或它们所说的任何东西，但这将是缩放的主要因素。

当你忽略原点附近的常数因子和东西时， Big-O 表示法（也称为 “渐近增长” 表示法）是“看起来像” 的功能 。我们用它来谈论事物的规模 。

基本

对于 “足够” 的大输入......

• f(x) ∈ O(upperbound)表示f “增长upperbound于” upperbound
• f(x) ∈ Ɵ(justlikethis)意味着f “完全像” justlikethis
• f(x) ∈ Ω(lowerbound)表示f “增长不低于” lowerbound

big-O 表示法并不关心常数因素：函数9x²被称为 “完全像10x² 。大 O 渐近符号也不关心非渐近的东西（“原点附近的东西” 或 “当问题大小很小时会发生什么”）：函数10x²被称为 “完全像10x² - x + 2 。

你为什么要忽略等式中较小的部分？因为当你考虑越来越大的尺度时，它们会被等式的大部分完全相形见绌; 他们的贡献变得相形见绌和无关紧要。 （见示例部分。）

换句话说，当你走向无限时，这就是比率 。 如果将实际时间除以O(...) ，您将获得大输入限制的常数因子。直觉上这是有道理的：如果你可以乘以一个来获得另一个，那么函数 “彼此缩放”。也就是说，当我们说......

actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

... 这意味着对于 “足够大” 的问题大小 N （如果我们忽略原点附近的东西），存在一些常数（例如 2.5，完全组成），这样：

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)

常数有很多种选择; 通常，“最佳” 选择被称为算法的 “常数因子”... 但我们经常忽略它，就像忽略非最大项一样（参见常数因子部分，为什么它们通常不重要）。你也可以把上面的等式想象成一个界限，说 “ 在最坏的情况下，它花费的时间永远不会比大约N*log(N) ，在 2.5 倍之内（我们不知道的常数因素）关心） “。

一般来说， O(...)是最有用的，因为我们经常关心最坏情况的行为。如果f(x)表示像处理器或内存使用一样 “坏” 的东西，那么 “ f(x) ∈ O(upperbound) ” 意味着 “ upperbound是处理器 / 内存使用的最坏情况”。

应用

作为纯粹的数学结构，big-O 表示法不仅限于讨论处理时间和内存。您可以使用它来讨论缩放有意义的任何事物的渐近性，例如：

• 一方中N人之间可能握手的次数（ Ɵ(N²) ，特别是N(N-1)/2 ，但重要的是它 “按比例缩放” N² ）
• 概率预期的一些人将某些病毒式营销视为时间的函数
• 网站延迟如何随 CPU 或 GPU 或计算机集群中的处理单元数量而变化
• CPU 上的热量输出如何随晶体管数量，电压等而变化。
• 作为输入大小的函数，算法需要运行多长时间
• 作为输入大小的函数，算法需要运行多少空间

例

对于上面的握手示例，一个房间里的每个人都会震动其他人的手。在那个例子中， #handshakes ∈ Ɵ(N²) 。为什么？

稍微补充一下：握手的数量恰好是 n-choose-2 或N*(N-1)/2 （N 个人中的每一个都握着 N-1 其他人的手，但是这个双手握手所以除以 2）：

然而，对于非常多的人来说，线性项N相形见绌并且有效地贡献了 0（在图表中：随着参与者的数量变大，对角线上的空盒子的总分数变得越来越小）。因此，缩放行为是order N² ，或者握手数 “增长为 N 2”。

#handshakes(N)
────────────── ≈ 1/2
     N²

就好像图表对角线上的空框（N *（N-1）/ 2 个复选标记）甚至不存在（N ^{2 个复选}标记渐近）。

（来自 “普通英语” 的临时题词:) 如果你想向自己证明这一点，你可以对比率进行一些简单的代数，将其分成多个术语（ lim意味着 “考虑到极限”，如果你在你还没有看到它，它只是 “和 N 真的很大” 的符号）：

N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

TL; 博士：握手很像 “X 2 这么多的大的值，如果我们写下的比例＃握手 / X 2，事实上，我们并不需要确切地 X 2 的握手甚至不露面的次数在十进制中任意大的时间。

例如，对于 x = 1 百万，比率＃handshakes /x²：0.499999 ...

建立直觉

这让我们发表如...... 的陈述

“对于足够大的输入 = N，无论常数因素是什么，如果我将输入大小 加倍 ......

• ... 我将 O（N）（“线性时间”）算法的时间加倍。“

  N →（2N）= 2（ N ）

• ...... 我的双平方（四）一 O（N²）（“二次时间”）算法所花费的时间。”（例如，有问题的 100 倍大需要 100²= 10000X 只要... 可能不可持续的）

  N² →（2N）²= 4（ N² ）

• ... O（N³）（“立方时间”）算法占用的时间是双立方（八倍）。“ （例如 100x 大的问题需要 100³= 1000000x 那么长...... 非常不可持续）

  cN³ →c（2N）³= 8（ cN³ ）

• ... 我在 O（log（N））（“对数时间”）算法所需的时间内添加固定数量。“ （便宜！）

  c log（N） →c log（2N）=（c log（2））+（ c log（N） ）=（固定量）+（ c log（N） ）

• ... 我没有改变 O（1）（“恒定时间”）算法所花费的时间。“ （最便宜！）

  c * 1 → c * 1

• ... 我 “（基本上）加倍”O（N log（N））算法所需的时间。“ （相当常见）

  它小于 O（N ^1.000001 ），你可能愿意称它基本上是线性的

• ...... 我可笑地增加了一个 O（2 ^N ）（“指数时间”）算法所花费的时间。“ （你只需要通过一个单位增加问题就可以加倍（或三倍等）时间）

  2 ^N →2 ^2N =（4 ^N ）............ 换句话说...... 2 ^N →2 ^{N + 1} = 2 ^N 2 ¹ = 2 2 ^N

[对于数学上的倾斜，你可以将鼠标悬停在破坏者身上以获得次要的注释]

（信用卡https://stackoverflow.com/a/487292/711085 ）

（从技术上讲，常数因素可能在一些更深奥的例子中很重要，但我已经在上面提到了一些事情（例如在 log（N）中），这样就没有了

这些是程序员和应用计算机科学家用作参考点的增长顺序。他们一直看到这些。 （因此，虽然你可以从技术上认为 “加倍输入会使 O（√N）算法慢 1.414 倍”，但最好将其视为 “这比对数更差但比线性更好”。）

不变因素

通常我们不关心具体的常数因素是什么，因为它们不会影响函数的增长方式。例如，两个算法可能都需要花费O(N)时间来完成，但是一个算法可能比另一个慢两倍。除非因素非常大，否则我们通常不会太在意，因为优化是棘手的业务（ 优化何时为时过早？ ）; 仅选择具有更好的大 O 的算法的行为通常会提高数量级的性能。

一些渐近优越的算法（例如，非比较O(N log(log(N)))排序可以具有如此大的常数因子（例如100000*N log(log(N)) ），或者相对较大的开销像O(N log(log(N)))隐藏+ 100*N ，即使在 “大数据” 上也很少使用它们。

为什么 O（N）有时是你能做的最好的，也就是为什么我们需要数据结构

如果您需要读取所有数据， O(N)算法在某种意义上是 “最佳” 算法。 读取一堆数据的行为是O(N)操作。将其加载到内存中通常是O(N) （如果您有硬件支持，则更快，如果您已经读过数据，则根本没有时间）。但是，如果您触摸或甚至查看每个数据（甚至每个其他数据），您的算法将花费O(N)时间来执行此查找。不管你的实际算法需要多长时间，它至少是O(N)因为它花了那么多时间查看所有数据。

写作的行为也是如此 。打印 N 个事物的所有算法将花费 N 次，因为输出至少那么长（例如，打印出所有排列（重新排列的方式）一组 N 个扑克牌是因子： O(N!) ）。

这促使了数据结构的使用：数据结构只需要读取一次数据（通常为O(N)时间），加上一些任意数量的预处理（例如O(N)或O(N log(N))或O(N²) ）我们试图保持小。此后，修改数据结构（插入 / 删除 / 等）并对数据进行查询只需很短的时间，例如O(1)或O(log(N)) 。然后，您继续进行大量查询！一般来说，你愿意提前做的工作越多，你以后做的工作就越少。

例如，假设您拥有数百万条道路段的纬度和经度坐标，并希望找到所有街道交叉口。

• 天真的方法：如果你有一个街道交叉口的坐标，并想要检查附近的街道，你每次都要经历数百万个段，并检查每个段是否相邻。
• 如果你只需要这样做一次，那么只需要做一次O(N)工作的天真方法就不会有问题，但如果你想做多次（在这种情况下， N次，一次用于每个段），我们必须做O(N²)工作，或 1000000²= 1000000000000 操作。不好（现代计算机每秒可以执行大约 10 亿次操作）。
• 如果我们使用一个称为哈希表的简单结构（即时速度查找表，也称为哈希表或字典），我们通过在O(N)时间内预处理所有内容来支付少量费用。此后，平均只需要通过其键查找一些东西（在这种情况下，我们的关键是纬度和经度坐标，四舍五入到网格; 我们搜索相邻的网格空间，其中只有 9，这是一个不变）。
• 我们的任务从一个不可行的O(N²)变成了一个可管理的O(N) ，我们所要做的就是支付一笔不小的费用来制作哈希表。
• 类比 ：在这种特殊情况下的类比是一个拼图游戏：我们创建了一个利用数据属性的数据结构。如果我们的路段就像拼图一样，我们会根据颜色和图案进行分组。然后我们利用它来避免以后做额外的工作（比较相似颜色的拼图，而不是每个其他单个拼图）。

故事的寓意：数据结构让我们加快了运营速度。更高级的数据结构可以让您以非常聪明的方式组合，延迟甚至忽略操作。不同的问题会有不同的类比，但它们都涉及以一种利用我们关心的某种结构的方式组织数据，或者我们人为地将其用于簿记。我们提前工作（基本上是计划和组织），现在重复的任务要容易得多！

实际例子：在编码时可视化增长顺序

渐近符号的核心是与编程完全分开。渐近符号是用于思考事物如何缩放的数学框架，并且可以在许多不同领域中使用。那就是说...... 这就是你如何将渐近符号应用于编码。

基础知识：每当我们与大小为 A 的集合中的每个元素（例如数组，集合，地图的所有键等）进行交互，或执行循环的迭代时，这是大小为 A 的乘数因子为什么我说 “乘法因子”？ - 因为循环和函数（几乎按定义）具有乘法运行时间：迭代次数，循环中完成的次数（或函数：你调用的次数）功能，在功能中完成的时间）。 （如果我们不做任何花哨的事情，例如跳过循环或提前退出循环，或者基于参数改变函数中的控制流，这是很常见的。这是一些可视化技术的示例，附带伪代码。

（这里， x s 代表恒定时间工作单位，处理器指令，解释器操作码，等等）

for(i=0; i<A; i++)        // A x ...
    some O(1) operation     // 1

--> A*1 --> O(A) time

visualization:

|<------ A ------->|
1 2 3 4 5 x x ... x

other languages, multiplying orders of growth:
  javascript, O(A) time and space
    someListOfSizeA.map((x,i) => [x,i])               
  python, O(rows*cols) time and space
    [[r*c for c in range(cols)] for r in range(rows)]

例 2：

for every x in listOfSizeA:   // A x ...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C x ...
        some O(1) operation       // 1

--> O(A*(1 + B + C))
    O(A*(B+C))        (1 is dwarfed)

visualization:

|<------ A ------->|
1 x x x x x x ... x

2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B  <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v

x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C  <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v

例 3：

function nSquaredFunction(n) {
    total = 0
    for i in 1..n:        // N x
        for j in 1..n:      // N x
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A x
        print(nSquaredFunction(a))  // A^2
}
// O(a^3)

如果我们做一些稍微复杂的事情，您仍然可以想象在视觉上发生了什么：

for x in range(A):
    for y in range(1..x):
        simpleOperation(x*y)

x x x x x x x x x x |
x x x x x x x x x   |
x x x x x x x x     |
x x x x x x x       |
x x x x x x         |
x x x x x           |
x x x x             |
x x x               |
x x                 |
x___________________|

在这里，您可以绘制的最小可识别轮廓是重要的; 三角形是二维形状（0.5 A ^ 2），就像正方形是二维形状（A ^ 2）; 两个常数因子保持在两者之间的渐近比例，但是我们忽略它就像所有因素一样......（这种技术有一些不幸的细微差别我不会在这里进行; 它会误导你。）

当然，这并不意味着循环和功能都很糟糕; 相反，它们是现代编程语言的基石，我们喜欢它们。但是，我们可以看到，我们将循环，函数和条件与我们的数据（控制流等）一起编织的方式模仿了我们程序的时间和空间使用！如果时间和空间的使用成为一个问题，那就是我们诉诸于聪明，找到一个我们没有考虑的简单算法或数据结构，以某种方式减少增长的顺序。尽管如此，这些可视化技术（尽管它们并不总是有效）可以让您在最坏情况下运行时进行初步猜测。

这是我们可以直观地认识到的另一件事：

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x

我们可以重新安排它，看看它是 O（N）：

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x

或者你可以对数据进行 log（N）次传递，对于 O（N * log（N））总时间：

<----------------------------- N ----------------------------->
 ^  x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
 |  x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
 |  x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
 v  x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x

不相关但值得一提：如果我们执行哈希（例如字典 / 哈希表查找），那就是 O（1）的因子。那很快。

[myDictionary.has(x) for x in listOfSizeA]
 \----- O(1) ------/    

--> A*1 --> O(A)

如果我们做一些非常复杂的事情，例如使用递归函数或分而治之算法， 你可以使用主定理 （通常是有效的），或者在荒谬的情况下使用 Akra-Bazzi 定理（几乎总是有效）你查找在维基百科上运行算法的时间。

但是，程序员并不这么认为，因为最终，算法直觉才成为第二天性。你将开始编写效率低下的东西，并立即想到 “我做的事情是非常低效的吗？ ”。如果答案是肯定的并且您预见它实际上很重要，那么您可以退一步思考各种技巧以使事情运行得更快（答案几乎总是 “使用哈希表”，很少 “使用树”，而且很少有点复杂的东西）。

摊销和平均案例复杂性

还有 “摊销” 和 / 或 “平均案例” 的概念（注意这些是不同的）。

平均情况 ：这不过是使用 big-O 表示法来表示函数的期望值，而不是函数本身。在通常情况下，您认为所有输入都具有相同的可能性，平均情况只是运行时间的平均值。例如，对于快速排序，即使最糟糕的情况是O(N^2)对于一些非常糟糕的输入，平均情况是通常的O(N log(N)) （真正糟糕的输入数量非常少，所以很少有人在平均情况下没有注意到它们。

分摊最坏情况 ：某些数据结构可能具有较大的最坏情况复杂性，但保证如果您执行许多这些操作，您执行的平均工作量将优于最坏情况。例如，您可能拥有通常需要持续O(1)时间的数据结构。然而，偶尔它会 '打嗝' 并花费O(N)时间进行一次随机操作，因为它可能需要做一些簿记或垃圾收集或其他东西...... 但它承诺，如果它打嗝，它不会又打了 N 次手术。最坏情况的成本仍然是每次操作的O(N) ，但是多次运行的摊销成本是每次操作的O(N)/N = O(1) 。由于大型操作非常罕见，因此可以考虑将大量的临时工作与其余工作融为一体。我们说这项工作是在大量的电话上 “摊销” 的，它渐渐消失了。

摊销分析的类比：

你开车了。偶尔，你需要花 10 分钟去加油站，然后花 1 分钟给油箱加油。如果你每次去汽车的任何地方都这样做（花 10 分钟开车到加油站，花几秒钟加满一加仑），效率会非常低。但是，如果你每隔几天填满一次坦克，开车到加油站的 11 分钟就会在足够多次的旅行中 “摊销”，你可以忽略它并假装你所有旅行的时间可能要长 5％。

平均案例和摊销最坏情况的比较：

• 平均情况：我们对输入做出一些假设; 即如果我们的输入具有不同的概率，那么我们的输出 / 运行时将具有不同的概率（我们取其平均值）。通常我们假设我们的输入都是同等可能的（均匀概率），但如果实际输入不符合我们对 “平均输入” 的假设，则平均输出 / 运行时计算可能毫无意义。如果你预期一致的随机输入，这是有用的思考！
• 摊销的最坏情况：如果你使用摊销的最坏情况数据结构，那么性能将保证在最终的最终情况下...... 最终（即使输入是由一个知道所有事情并且正在努力的邪恶恶魔选择的）把你搞砸了。通常我们使用它来分析算法，这些算法在性能上可能非常 “不连贯”，出现意外的大型打嗝，但随着时间的推移，其性能与其他算法一样好。 （但是，除非你的数据结构有许多优秀工作的上限，否则它是否愿意拖延，一个邪恶的攻击者可能会迫使你一次性赶上最大量的拖延工作。

但是，如果您合理地担心攻击者，除了摊销和平均情况外，还有许多其他算法攻击向量需要担心。）

平均案例和摊销都是非常有用的工具，可以考虑到扩展的思考和设计。

（如果对此子主题感兴趣，请参阅平均案例和摊销分析之间的差异 。）

多维大 O.

大多数时候，人们没有意识到工作中有多个变量。例如，在字符串搜索算法中，您的算法可能需要时间O([length of text] + [length of query]) ，即它在两个变量（如O(N+M)是线性的。其他更天真的算法可以是O([length of text]*[length of query])或O(N*M) 。忽略多个变量是我在算法分析中看到的最常见的疏忽之一，并且在设计算法时可能会妨碍您。

整个故事

请记住，大 O 不是整个故事。您可以通过使用缓存来大幅加速某些算法，使其无法缓存，通过使用 RAM 而不是磁盘来避免瓶颈，使用并行化或提前完成工作 - 这些技术通常独立于增长顺序 “big-O” 符号，尽管你经常会看到并行算法的大 O 符号中的核心数量。

还要记住，由于程序的隐藏约束，您可能并不真正关心渐近行为。您可能正在使用有限数量的值，例如：

• 如果你要对 5 个元素进行排序，你不想使用快速的O(N log(N))快速排序; 你想使用插入排序，这恰好在小输入上表现良好。这些情况经常出现在分而治之的算法中，在这种算法中，您将问题分解为越来越小的子问题，例如递归排序，快速傅里叶变换或矩阵乘法。
• 如果某些值由于某些隐藏的事实而被有效限制（例如，平均人名在 40 个字母处受到轻微限制，并且人类年龄在 150 左右受到轻微限制）。您还可以在输入上强加边界以有效地使术语保持不变。

实际上，即使在具有相同或相似渐近性能的算法中，它们的相对优点实际上也可能由其他因素驱动，例如：其他性能因素（快速排序和合并排序都是O(N log(N)) ，但是快速排序需要 CPU 缓存的优点）; 非性能考虑因素，如易于实施; 是否有可用的库，以及库的信誉和维护程度。

在 500MHz 计算机和 2GHz 计算机上，程序运行速度也会变慢。我们并不认为这是资源边界的一部分，因为我们考虑了机器资源（例如每个时钟周期）的缩放，而不是实际的秒。但是，有类似的东西可以 “秘密” 影响性能，例如您是否在仿真下运行，或者编译器是否优化了代码。这些可能会使一些基本操作花费更长时间（甚至相对于彼此），甚至可以渐进地加速或减慢某些操作（甚至相对于彼此）。在不同的实现和 / 或环境之间效果可能很小或很大。你切换语言或机器来勉强做一点额外的工作吗？这取决于其他一百个原因（必要性，技能，同事，程序员的生产力，你的时间的货币价值，熟悉程度，变通方法，为什么不装配或 GPU 等等），这可能比性能更重要。

上述问题，如编程语言，几乎从未被视为常数因素的一部分（也不应该是）; 但是人们应该意识到它们，因为有时 （尽管很少）它们可能会影响事物。例如，在 cpython 中，本机优先级队列实现渐近非最优（ O(log(N))而不是O(1)用于选择插入或 find-min）; 你使用其他实现吗？可能不是，因为 C 实现可能更快，并且其他地方可能存在其他类似问题。有权衡; 有时他们很重要，有时他们不重要。

（ 编辑 ：“普通英语” 解释在这里结束。）

数学附录

为了完整性，big-O 表示法的精确定义如下： f(x) ∈ O(g(x))表示 “f 渐近上限为 const * g”：忽略 x 的某些有限值以下的所有内容，存在|f(x)| ≤ const * |g(x)|的常数|f(x)| ≤ const * |g(x)| 。 （其他符号如下：就像O表示≤， Ω表示≥。有小写变体： o表示 <，而ω表示 >。） f(x) ∈ Ɵ(g(x))表示f(x) ∈ O(g(x))和f(x) ∈ Ω(g(x)) （上限和下限由 g）：存在一些常数，使得 f 总是位于const1*g(x)之间的 “带” 中const1*g(x)和const2*g(x) 。它是你可以做出的最强的渐近陈述，大致相当于== 。 （对不起，为了清楚起见，我选择延迟提到绝对值符号到现在为止; 特别是因为我从未在计算机科学背景中看到过负面的价值观。）

人们经常使用= O(...) ，这可能是更正确的'comp-sci' 符号，并且完全合法使用...... 但是应该意识到=不被用作平等; 它是一个复合符号，必须被解读为成语。我被教导使用更严格的∈ O(...) 。 ∈表示 “是” 的一个元素。 O(N²)实际上是一个等价类 ，也就是说，它是一组我们认为是相同的东西。在这种特殊情况下， O(N²)包含 { 2 N² ， 3 N² ， 1/2 N² ， 2 N² + log(N) ， - N² + N^1.9 ，......} 等元素并且无限大，但它是还是一套。 =符号可能是更常见的，甚至被世界着名的计算机科学家用在论文中。此外，通常的情况是，在一个随意的环境中，人们会在他们的意思是Ɵ(...)时说O(...) Ɵ(...) ; 这在技术上是正确的，因为一组事物Ɵ(exactlyThis)是O(noGreaterThanThis)一个子集O(noGreaterThanThis) ...... 并且它更容易输入。 ;-)