“大O”符号的简单英文解释是什么？

2018-05-28 23:00:46

我宁愿尽可能少的正式定义和简单的数学。

快速的说明，这几乎可以肯定，Theta符号（这是一个双边界）中的大O符号（这是一个上界）令人困惑。根据我的经验，这实际上是非学术环境下的典型讨论。对造成的任何混淆抱歉。

大图O的复杂性可以用这个图形来显示：

大O分析

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

大O符号是算法复杂性的相对表示。

在这句话中有一些重要的和故意选择的单词：

相对：你只能比较苹果和苹果。您无法将算术乘法算法与排序整数列表的算法进行比较。但是比较两种算法来进行算术运算（一次乘法，一次加法）会告诉你一些有意义的事情;

表示法： Big-O（以其最简单的形式）将算法之间的比较缩减为单个变量。该变量是根据观察结果或假设进行选择的。例如，通常基于比较操作比较排序算法（比较两个节点以确定它们的相对排序）。这假定比较是昂贵的。但如果比较便宜但交换成本高昂呢？它改变了比较; 和

复杂性：如果需要我一秒钟对10,000种元素进行排序，需要多长时间才能筛选出100万个元素？这种情况下的复杂性是对其他事物的相对衡量。

当你读完其余部分时，请重新阅读上述内容。

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

加成;

减法;

乘法; 和

师。

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

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

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

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

减法是相似的（除了你可能需要借钱而不是进账）。

乘法是不同的。你把这些数字加起来，把底部数字中的第一个数字与顶部数字中的每个数字相乘，再依次乘以每个数字。所以要乘以我们的两个6位数字我们必须做36次乘法。我们可能需要执行多达10或11列的添加才能获得最终结果。

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

由于该算法与n平方成比例，这是O（n2）或二次方复杂度 。这是介绍另一个重要概念的好时机：

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

精明的人可能已经意识到我们可以将操作次数表示为：n2 + 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（base e），log10，log2或其他一些基数。它没有关系，它仍然是O（log n），就像O（2n2）和O（100n2）仍然是O（n2）。

在这一点上值得解释的是，可以使用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是等价的，因为它们使用相同的道路，反之亦然）。

实际上有三种可能性。

把这个带到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×1064

所以旅行推销员问题的大O是O（n！）或阶乘或组合复杂性 。

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

需要思考的东西。

多项式时间

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

O（n），O（n2）等都是多项式时间。有些问题不能在多项式时间内解决。正因为如此，世界上才会使用某些东西。公钥密码学是一个很好的例子。在计算上很难找到非常大数量的两个主要因素。如果不是，我们不能使用我们使用的公钥系统。

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

它显示了算法如何缩放。

O（n2） ：称为二次型复杂度

1项：1秒

10项：100秒

100项：10000秒

注意物品的数量增加了10倍，但时间增加了102倍。基本上，n = 10，所以O（n2）给我们的比例系数n2为102。

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 。

这是它的要点。它们减少了数学运算，所以它可能不完全是n2或他们所说的数字，但这将成为缩放的主要因素。

大O符号（也称为“渐近式增长”符号）是当忽略常量因素和原点附近的东西时，“看起来像什么”的函数。我们用它来谈论事物的规模 。

基本

为“足够”大的输入...

f(x) ∈ O(upperbound)意味着f “增长upperbound于” upperbound

f(x) ∈ Ɵ(justlikethis)意味着f “生长得像” justlikethis

f(x) ∈ Ω(lowerbound)意味着f “增长不低于” lowerbound

大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是处理器/内存使用情况的最坏情况”。

应用

作为纯粹的数学结构，大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个复选标记）不在那里（渐近地N2校验标记）。

（从“简单的英语”中暂时离题:)如果你想向自己证明这一点，你可以在比例上执行一些简单的代数，将其分解为多个项（ 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; dr：握手的数量'看起来像'x 2'对于大数值来说非常重要，如果我们要写下比率＃握手/ x 2，那么我们并不需要完全x 2握手的事实甚至不会显示出来在任意大的时候小数。

例如，对于x = 100万，比率＃握手/ x 2：0.499999 ...

建设直觉

这让我们可以做出如下陈述...

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

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

N →（2N）= 2（ N ）

...我将O（N²）（“二次时间”）算法所花费的时间加倍（四倍）。“（例如，100x的问题大到需要100²= 10000x长......可能不可持续）

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

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

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

...我给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（N1.000001），你可能愿意调用基本上线性的

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

2N →22N =（4N）............换句话说...... 2N →2N + 1 = 2N21 = 2 2N

[对于数学上倾斜的，你可以将鼠标放在扰流板上，用于小副标题]

（信贷到https://stackoverflow.com/a/487292/711085）

（从技术上讲，恒定因素可能在一些更深奥的例子中可能很重要，但我已经说过上面的东西（例如在log（N）中），以致它不会）

这些是程序员和应用计算机科学家用作参考点的面包和奶油增长的顺序。他们一直在看这些。（所以，尽管你可以从技术上思考“将输入加倍使得O（√N）算法慢1.414倍”，但最好将它想象为“这比对数更糟，但比线性更好”）。

常数因素

通常我们不关心具体的常数因素是什么，因为它们不影响函数增长的方式。例如，两种算法可能都需要O(N)时间才能完成，但其中一个可能会比另一个慢两倍。我们通常不会太在意，除非因素非常大，因为优化是棘手的业务（何时优化过早？单纯采用更好的big-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次迭代，这是大小为A的乘法因子。为什么我要说“乘法因子”？ - 因为循环和函数（几乎按定义）具有乘法运行时间：迭代次数，循环中完成的工作次数（或函数：您调用的次数功能，时间在功能上完成的工作）。（如果我们不做任何奇怪的事情，例如跳过循环或提前退出循环，或者根据参数更改函数中的控制流，这很常见）。下面是可视化技术的一些示例，并带有伪代码。

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

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

或者，也许你会记录（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定理（几乎总是有效的）在维基百科上运行你的算法的时间。

但是，程序员并不这样认为，因为最终，算法直觉只是成为第二性质。你将开始编写效率低下的代码，并立即想到“我在做一些效率低下的事情吗？ ”。如果答案是“是”，并且您预见它实际上是重要的，那么您可以退后一步，想出各种方法让事情运行得更快（答案几乎总是“使用散列表”，很少“使用树”，而且很少有更复杂的东西）。

摊销和平均情况的复杂性

还有“摊销”和/或“平均情况”的概念（请注意这些不同）。

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

已摊销的最差情况 ：某些数据结构可能具有较大的最坏情况复杂度，但保证如果您执行了许多这些操作，那么您所做的平均工作量将会比最差情况下的要好。例如，您可能有一个通常需要不断的O(1)时间的数据结构。然而，偶尔它会'打嗝'并将O(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而不是磁盘，使用并行化或提前完成工作来避免瓶颈 - 这些技术通常独立于增长顺序“大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实现可能更快，并且其他地方可能还有其他类似的问题。有折衷; 有时它们很重要，有时它们不重要。

（编辑：“纯英文”的解释到此为止。）

数学附录

为了完整性，大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)之间的“band” 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) 1/2 N² 2 N² + log(N) ， - N² + N^1.9 ，...}等元素并且无限大，但它仍然是一套。该=符号可能是比较常见的，并且即使在由世界著名的计算机科学家的论文中。另外，通常情况下，在一个偶然的环境中，当他们的意思是Ɵ(...)时，人们会说O(...) Ɵ(...) ; 这在技术上是正确的，因为set Ɵ(exactlyThis)的集合是O(noGreaterThanThis)一个子集，并且它更容易输入。 ;-)

链接地址: http://www.djcxy.com/p/85.html

上一篇: What is a plain English explanation of "Big O" notation?

下一篇: How do I remove a property from a JavaScript object?