“Big O” 符号的简单英语解释是什么?

我希望尽可能少用正式的定义和简单的数学方法。

答案

快速说明,这几乎肯定会使Big O 表示法 (上限)与 Theta 表示法 “Θ”(两侧界线)混淆。以我的经验,这实际上是非学术场合中讨论的典型内容。造成任何混乱,我们深表歉意。


此图可以直观地显示 O 的复杂性:

大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 12 )乘法和 200 万加法。

随着算法按 n 平方缩放,这就是O(n 2二次复杂度 。现在是引入另一个重要概念的好时机:

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

机敏的人可能已经意识到我们可以将操作数表示为:n 2 + 2n。但是,正如您从我们的示例中看到的那样,每个例子中有两个百万位数字,第二项(2n)变得微不足道(占该阶段总操作数的 0.0002%)。

可以注意到,我们在这里假设了最坏的情况。在将 6 位数字相乘时,如果其中之一具有 4 位数字,而另一个具有 6 位数字,则我们只有 24 个乘法。尽管如此,我们仍会计算该 n 的最坏情况,即当两者均为 6 位数字时。因此,Big-O 表示法是关于算法的最坏情况。

电话簿

我能想到的下一个最佳示例是电话簿,通常称为 “白页” 或类似内容,但因国家 / 地区而异。但是我说的是按姓氏,名字首字母或名字,可能的地址和电话号码列出的人。

现在,如果您指示计算机在包含 1,000,000 个名字的电话簿中查找 “John Smith” 的电话号码,您将怎么办?忽略了一个事实,即您可以猜测 S 的开始距离(假设您不能),那么您会怎么做?

一个典型的实现方式可能是打开中间位置,占据第 500,000 个位置并将其与 “Smith” 进行比较。如果碰巧是 “史密斯,约翰”,我们真的很幸运。 “John Smith” 更可能在该名称之前或之后。如果在此之后,则将电话簿的后半部分一分为二并重复。如果在此之前,那么我们将电话簿的前半部分分成两半,然后重复。等等。

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

因此,如果您想在一百万个电话簿中找到一个名字,则最多可以执行 20 次,实际上可以找到任何名字。在比较搜索算法时,我们认为此比较是我们的 “n”。

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

那真是太好了,不是吗?

用 Big-O 术语来说,这是O(log n)对数复杂度 。现在所讨论的对数可以是 ln(底数 e),log 10 ,log 2或其他一些底数。就像 O(2n 2 )和 O(100n 2 )都是 O(n 2 )一样,它仍然是 O(log 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 64

因此,旅行推销员问题的 Big-O 是O(n!)阶乘或组合复杂度

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

需要考虑的事情。

多项式时间

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

O(n),O(n 2 )等都是多项式时间。一些问题无法在多项式时间内解决。因此,世界上使用了某些东西。 公钥密码术就是一个很好的例子。在计算上很难找到数量很大的两个主要因素。如果不是,我们将无法使用所使用的公钥系统。

无论如何,这就是我对 Big O(修订本)的解释(希望是纯英语)。

它显示了算法如何根据输入大小进行缩放。

O(n 2 :称为二次复杂度

  • 1 项:1 秒
  • 10 件:100 秒
  • 100 项:10000 秒

请注意,项目数增加了 10 倍,但时间增加了 10 2倍。基本上,n = 10,所以 O(n 2 )给我们缩放因子 n 2 ,它是 10 2

O(n) :称为线性复杂度

  • 1 项:1 秒
  • 10 件:10 秒
  • 100 件:100 秒

这次,项目数增加了 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的对n就是所需的时间,因此为log n

这就是要旨。他们降低了数学运算的精度,因此可能不是正好是 n 2或他们所说的那样,但这将是缩放的主要因素。

当您忽略恒定因素和原点附近的东西时, Big-O 表示法(也称为 “渐近生长” 表示法)的作用是“看起来像” 。我们用它来谈论事物如何扩展


基本

用于 “足够” 的大投入...

  • f(x) ∈ O(upperbound)意味着f “增长upperbound于” upperbound
  • f(x) ∈ Ɵ(justlikethis)平均f “正是变得像” justlikethis
  • f(x) ∈ Ω(lowerbound)表示f “增长不慢于” lowerbound

big-O 表示法不关心常量因素:函数9x²据说 “完全像10x²一样增长”。 big-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 ,但重要的是它的缩放比例类似于
  • 将病毒性营销视为时间的函数的预期概率人数
  • 网站等待时间如何随 CPU 或 GPU 或计算机群集中的处理单元数量扩展
  • CPU 上的热量输出比例如何随晶体管数量,电压等的变化而消失。
  • 一个算法需要运行多少时间,取决于输入大小
  • 算法需要运行多少空间,取决于输入大小

对于上面的握手示例,房间中的每个人都与其他人握手。在该示例中, #handshakes ∈ Ɵ(N²) 。为什么?

稍微备份一下:握手的次数恰好是 n-choose-2 或N*(N-1)/2 (每 N 个人握手 N-1 个其他人的握手,但是这种重复计算的握手次数除以 2):

每个人都与其他人握手。根据Wikipedia / Wikimedia Commons“完整图表”文章的图像信用和许可。 邻接矩阵

但是,对于非常多的人,线性项N相形见 and,并有效地使比率为 0(在图表中:随着参与者数量的增加,对角线上的空框在总框上所占的比例会变小)。因此,缩放行为为order N² ,或者握手次数 “像 N² 一样增长”。

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

好像图表对角线上的空白框(N *(N-1)/ 2 个复选标记)甚至没有(N 2 个复选标记渐近)一样。

(与 “普通英语” 暂时偏离:)如果您想向自己证明这一点,则可以对比率进行一些简单的代数运算,以将其分解为多个项( lim表示 “被认为是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 百万,比率#握手 / x²:0.499999 ...


建立直觉

这使我们可以像...

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

  • ... 我将 O(N)(“线性时间”)算法花费的时间加倍。”

    N →(2N)= 2( N

  • ... 我将 O(N²)(“二次时间”)算法所花费的时间加倍(四倍)。” (例如,问题的 100 倍大需要 100²= 10000 倍长…… 可能是不可持续的)

    →(2N)²= 4(

  • ... 我将 O(N³)(“立方时间”)算法所花费的时间加倍(八倍)。” (例如,问题的 100 倍大需要 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 * 1c * 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 1 = 2 2 N

[对于数学上的倾向,您可以将鼠标悬停在扰流板上以找到较小的旁注]

(感谢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 运算。不好(一台现代计算机每秒可以执行约十亿次操作)。
  • 如果我们使用称为哈希表(即时速度查找表,也称为哈希图或字典)的简单结构,则通过在O(N)时间内对所有内容进行预处理,我们将付出很小的代价。此后,平均仅需花费固定时间即可通过其键查找内容(在这种情况下,我们的键是经度和纬度坐标,四舍五入为一个网格;我们搜索相邻网格空间中只有 9 个,这是一个不变)。
  • 我们的任务从无法实现的O(N²)变为可管理的O(N) ,而我们要做的就是花很少的钱来制作哈希表。
  • 类比 :在此特定情况下的类比是一个拼图游戏:我们创建了一个利用数据某些属性的数据结构。如果我们的路段像拼图一样,我们通过匹配颜色和图案将它们分组。然后,我们利用它来避免以后做额外的工作(将颜色相似的拼图相互比较,而不是将每个拼图相互比较)。

故事的寓意:数据结构使我们加快了运营速度。更高级的数据结构可以使您以难以置信的巧妙方式组合,延迟甚至忽略操作。不同的问题会有不同的类推,但它们都涉及以一种利用我们关心的结构或为簿记而人为地施加某种结构的方式来组织数据。我们会提前进行工作(基本上是计划和组织),现在重复执行的任务要容易得多!


实际示例:在编码时可视化增长顺序

渐进符号的本质与编程完全不同。渐近符号是一种思考事物如何缩放并可以在许多不同领域中使用的数学框架。就是说... 这就是渐近符号应用于编码的方式。

基础知识:每当我们与大小为 A 的集合中的每个元素进行交互(例如数组,集合,映射的所有键等),或执行循环 A 的迭代时,即大小 A 的乘法因子。为什么说 “乘法因子”?–因为循环和函数(几乎是按定义)具有乘法运行时间:迭代次数,循环中完成的工作时间(或对于函数:调用次数)功能,乘以在该功能中完成的工作)。 (这很普遍,如果我们不做任何花哨的事情,例如跳过循环或尽早退出循环,或者基于参数更改函数中的控制流,这是很常见的。)这是一些可视化技术示例,带有伪代码。

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

for(i=0; i<A; i++)        // A * ...
    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 * (...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C * (...
        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 *
        for j in 1..n:      // N *
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A *
        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 定理(几乎总是有效)来查找您的算法在 Wikipedia 上的运行时间。

但是,程序员并不这样认为,因为最终,算法直觉只是第二天性。您将开始编写效率低下的代码,然后立即想到 “我在做效率低下的事情吗? ”。如果答案是 “是”,并且您认为它确实很重要,那么您可以退后一步,想出各种使事情运行更快的技巧(答案几乎总是 “使用哈希表”,很少使用 “使用树”,而且很少有更复杂的东西)。


摊销和平均情况下的复杂性

还有 “摊销” 和 / 或 “平均情况” 的概念(请注意,它们是不同的)。

平均情况 :这仅是对函数的期望值使用 big-O 表示法,而不是对函数本身使用。在通常情况下,您认为所有输入的可能性均等,平均情况只是运行时间的平均值。例如,对于快速排序,即使对于某些真正糟糕的输入,最坏的情况是O(N^2) ,但通常情况下是通常的O(N log(N)) (真正糟糕的输入的数量非常小,因此在一般情况下,我们很少会注意到它们)。

摊销最坏情况 :某些数据结构可能具有最坏情况的复杂性,但是要保证,如果您执行许多此类操作,则平均工作量将比最坏情况要好。例如,您可能具有通常需要恒定O(1)时间的数据结构。但是,偶尔它会 “打 cup” 并花O(N)时间进行一次随机操作,因为也许它需要做一些簿记或垃圾收集之类的工作…… 但是它向您保证,如果打 h,它不会再次打 N,需要进行 N 次以上的操作。最坏的情况下,每次操作的成本仍为O(N) ,但多次运行的摊销成本为O(N)/N = O(1) 。由于大型操作非常罕见,因此可以将大量的偶然工作与其他工作融合为一个恒定因素。我们说该作品在足够多的通话中被 “摊销”,以至于渐渐消失。

摊销分析的类比:

你开汽车。有时,您需要花费 10 分钟去加油站,然后花费 1 分钟为储罐加气。如果您每次开车去任何地方都这样做(花 10 分钟车程到加油站,花几秒钟填充一加仑的油),这将是非常低效的。但是,如果您每隔几天就给油箱加油一次,那么开车到加油站所花费的 11 分钟便会在足够多的行程中 “摊销”,您可以忽略它并假装所有行程可能要长 5%。

平均情况与摊销最坏情况之间的比较:

  • 平均情况:我们对输入进行一些假设;即,如果我们的输入具有不同的概率,那么我们的输出 / 运行时将具有不同的概率(我们取其平均值)。通常,我们假设所有输入均具有相同的可能性(均等概率),但是如果实际输入不符合我们对 “平均输入” 的假设,则平均输出 / 运行时计算可能毫无意义。但是,如果您期望统一的随机输入,则可以考虑一下!
  • 摊销后的最坏情况:如果使用摊销后的最坏情况数据结构,则性能可以保证在摊销后的最坏情况之内... 最终(即使输入是由了解所有情况并试图搞砸了)。通常,我们用它来分析那些性能可能非常 “不稳定” 且出现意外大打 algorithms 的算法,但是随着时间的推移,它的性能与其他算法一样好。 (但是,除非您的数据结构对其愿意拖延的许多出色工作有上限,否则邪恶的攻击者可能会强迫您一次全部追赶最大的拖延工作量。

不过,如果您合理地担心攻击者,那么除摊销和平均情况外,还有许多其他算法攻击媒介值得担心。)

平均用例和摊销都是在考虑和考虑比例时非常有用的工具。

(如果对此子主题感兴趣,请参阅平均案例与摊销分析之间的差异 。)


多维 big-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 表示法中看到内核数,但是使用 “big-O” 表示法。

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

  • 如果要对 5 个元素进行排序,则不希望使用快速的O(N log(N))快速排序。您想使用插入排序,而插入排序恰好在较小的输入上表现良好。这些情况通常在分而治之的算法中出现,您可以将问题分解为越来越小的子问题,例如递归排序,快速傅立叶变换或矩阵乘法。
  • 如果由于某些隐藏的事实而使某些值有效地受到限制(例如,一般的人名柔和地限制在 40 个字母左右,而人的年龄则柔和地限制在 150 个左右)。您还可以在输入上加上界限,以有效地使术语保持不变。

实际上,即使在具有相同或相似渐近性能的算法中,它们的相对价值实际上也可能受其他因素驱动,例如:其他性能因素(quicksort 和 mergesort 均为O(N log(N)) ,但 quicksort 需要 CPU 缓存的优势);非性能方面的考虑因素,例如易于实施;库是否可用以及库的信誉和维护程度。

程序在 500MHz 计算机上的运行速度也将比 2GHz 计算机上的运行慢。我们实际上并不认为这是资源范围的一部分,因为我们考虑的是机器资源(例如,每个时钟周期)而不是每秒的扩展。但是,有些类似的事情会 “秘密地” 影响性能,例如您是否在仿真下运行,或者编译器是否优化了代码。这些可能会使一些基本操作花费更长的时间(甚至相对于彼此),甚至可能渐近地(甚至相对于彼此)加快或减慢某些操作。在不同的实现和 / 或环境之间,效果可能很小或很大。您是否切换语言或机器以节省一点额外的工作?这取决于其他一百个原因(必要性,技能,同事,程序员的工作效率,时间的金钱价值,熟悉程度,变通办法,为什么不使用汇编或 GPU 等),这可能比性能更重要。

上述问题,就像选择哪种编程语言的效果一样,几乎永远不会被视为恒定因素的一部分(也不应该)。但人们应该意识到它们,因为有时 (尽管很少)它们可能会影响事物。例如,在 cpython 中,本机优先级队列实现是渐近非最优的(对于您选择插入还是 find-min 来说,是O(log(N))而不是O(1) );您是否使用其他实现?可能不是,因为 C 的实现可能更快,并且其他地方可能还有其他类似的问题。需要权衡;有时它们很重要,有时却不重要。


编辑 :“普通英语” 的解释到此结束。)

数学附录

为了完整起见,big-O 表示法的精确定义如下: f(x) ∈ O(g(x))表示 “f 由 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” 表示法,并且完全合法使用;读为 “f = O(...)”,“f 是阶... / f 由... xxx 包围”,并且被认为是 “f 是渐近性为... 的某些表达式”。有人教我使用更严格的∈ O(...)表示 “是的元素”(仍然如前所述)。在这种情况下, O(N²)包含 { 2 N²3 N²1/2 N²2 N² + log(N)- N² + N^1.9 ,...} 之类的元素,并且无限大,但是还是一套。

O 和Ω不对称(n = O(n²),但 n² 不是 O(n)),但是Ɵ是对称的,并且(因为这些关系都是传递和自反的)Ɵ因此是对称的,传递和自反的,因此将所有函数的集合划分为等效类 。等效类是我们认为相同的一组事物。这就是说,给定您可以想到的任何功能,您都可以找到该类的规范 / 唯一的 “渐近代表”(通常以限制为限... 我认为 );就像您可以将所有整数分组为偶数或偶数一样,您可以将所有带有Ɵ的函数分组为 x-ish,log(x)^ 2-ish 等,通过基本忽略较小的项(但有时您可能会陷入困境)更复杂的功能,它们本身就是单独的类)。

=符号可能是更常见的一种,甚至被世界著名的计算机科学家在论文中使用。另外,通常情况下,在随意的环境中,人们说 mean O(...)时会说O(...) Ɵ(...) ;从技术上讲这是正确的,因为事物集Ɵ(exactlyThis)O(noGreaterThanThis)的子集... 并且更容易键入。 ;-)

编辑:快速说明,这几乎肯定会使Big O 表示法 (这是一个上限)与 Theta 表示 (这是一个上下限)混淆。以我的经验,这实际上是非学术场合中讨论的典型内容。造成任何混乱,我们深表歉意。

一句话:随着工作规模的扩大,完成工作需要多长时间?

显然,这仅使用 “大小” 作为输入,而使用 “花费的时间” 作为输出—如果您想谈论内存使用情况等,也可以使用相同的想法。

这是一个示例,其中我们有 N 件 T 恤要干燥。我们假定将它们置于干燥位置非常快(即,与人的互动可以忽略不计)。当然,现实生活中并非如此...

  • 在室外使用清洗线:假设您有无限大的后院,则清洗会在 O(1)时间内烘干。无论您拥有多少,它都会得到相同的阳光和新鲜空气,因此大小不会影响干燥时间。

  • 使用滚筒式干衣机:每次装载 10 件衬衫,一个小时后完成。 (忽略此处的实际数字,它们是无关紧要的。)因此,烘干 50 件衬衫所需的时间大约是烘干 10 件衬衫所需时间的 5 倍。

  • 将所有物品放到通风的橱柜中:如果将所有物品放到一大堆中并让整体保暖,中衬衫要花很长时间才能变干。我不想猜测细节,但我怀疑这至少是 O(N ^ 2)- 随着洗涤量的增加,干燥时间增加得更快。

“大 O” 表示法的一个重要方面是,它并未说明哪种算法在给定大小下会更快。拿一个哈希表(字符串键,整数值)和一个对数组(字符串,整数)。根据字符串在哈希表中查找键或在数组中查找元素是否更快? (即对于数组,“在字符串部分与给定键匹配的地方找到第一个元素。”)哈希表通常被摊销(〜=“平均”)O(1)—一旦建立,就应该花费大约同时在 100 条目表中查找条目的时间与在 1,000,000 条目表中查找条目的时间相同。在数组中找到一个元素(基于内容而不是索引)是线性的,即 O(N)- 平均而言,您将不得不查看条目的一半。

这会使哈希表比查找数组快吗?不必要。如果条目的集合很小,则数组可能会更快 - 您可以在计算所要查找的哈希码所需的时间内检查所有字符串。但是,随着数据集的增大,哈希表最终将击败该数组。

大 O 描述了当输入变大时函数的增长行为(例如程序的运行时)的上限。

例子:

  • O(n):如果我将输入大小加倍,则运行时间将加倍

  • O(n 2 ):如果输入大小加倍运行时间四倍

  • O(log n):如果输入大小加倍,则运行时间增加一

  • O(2 n ):如果输入大小增加一,则运行时会加倍

输入大小通常是表示输入所需的空间(以位为单位)。

程序员最常使用 Big O 表示法来近似表示度量(算法)完成所需时间,以输入集大小的函数表示。

大 O 有助于比较两种算法随着输入数量增加而扩展的程度。

更确切地说, Big O 表示法用于表达函数的渐近行为。这意味着函数在接近无穷大时的行为。

在许多情况下,算法的 “O” 将属于以下情况之一:

  • O(1) - 完成时间是相同的,与输入集的大小无关。一个示例是按索引访问数组元素。
  • O(Log N) - 完成时间大致与 log2(n)一致。例如,1024 个项目花费的时间大约是 32 个项目的两倍,因为 Log2(1024)= 10 且 Log2(32)=5。一个示例是在二进制搜索树 (BST)中查找一个项目。
  • O(N) - 完成时间与输入集的大小成线性比例。换句话说,如果将输入集中的项数加倍,则该算法所需的时间大约是原来的两倍。一个示例是计算链接列表中的项目数。
  • O(N Log N) - 完成时间增加的项目数乘以 Log2(N)的结果。一个例子就是堆排序快速排序
  • O(N ^ 2) - 完成时间大致等于项数的平方。一个例子就是冒泡排序
  • O(N!) - 完成时间是输入集的阶乘。一个例子就是旅行推销员问题暴力解决方案

大 O 会忽略在输入大小朝无穷大增加时不会对功能的增长曲线产生有意义影响的因素。这意味着添加或乘以该函数的常量将被忽略。

Big O 只是一种以一种常见的方式 “表达” 自己的方式,即 “运行我的代码需要多少时间 / 空间?”。

您可能经常看到 O(n),O(n 2 ),O(nlogn)等,所有这些只是显示方式;算法如何变化?

O(n)表示 Big O 为 n,现在您可能会想,“n!” 是什么?那么 “n” 是元素的数量。要在阵列中搜索项目的映像。您将不得不查看每个元素,并将其显示为 “您是否正确的元素 / 项目?” 在最坏的情况下,该项目位于最后一个索引处,这意味着它花费的时间与列表中的所有项目一样多。因此,一般来说,我们说 “哦,嘿,n 是一个给定的值!” 。

因此,您可能会理解 “ n 2 ” 的含义,但更具体地讲,请您以为您拥有简单,最简单的排序算法;泡泡糖该算法需要仔细检查每个项目的整个列表。

我的列表

  1. 1 个
  2. 6
  3. 3

这里的流程将是:

  • 比较 1 和 6,哪个最大? Ok 6 位置正确,继续前进!
  • 比较 6 和 3,哦,3 少!让我们移动一下,确定列表已更改,我们需要从头开始!

这是 O n 2,因为您需要查看列表中所有包含 “n” 个项目的项目。对于每个项目,您再次查看所有项目,以进行比较,这也是 “n”,因此对于每个项目,您查看 “n” 次,这意味着 n * n = n 2

我希望这是您想要的那样简单。

但是请记住,Big O 只是一种以时间和空间方式表现自己的方式。

大 O 描述了算法的基本缩放性质。

Big O 并没有告诉您很多关于给定算法的信息。它切开了骨头,仅提供有关算法可缩放性的信息,特别是响应 “输入大小” 算法的资源使用(思考时间或内存)如何缩放。

考虑一下蒸汽机和火箭之间的区别。它们不仅是同一事物的不同变体(例如普锐斯(Prius)引擎还是兰博基尼(Lamborghini)引擎),而且它们的核心是截然不同的推进系统。蒸汽机可能比玩具火箭快,但是没有蒸汽活塞机能够达到轨道运载火箭的速度。这是因为这些系统在达到给定速度(“输入大小”)所需的燃料(“资源使用”)的关系方面具有不同的缩放特性。

为什么这个这么重要?因为软件处理的问题的大小差异可能高达一万亿美元。考虑一下。登月所需的速度与人的行走速度之间的比小于 10,000:1,与软件可能面对的输入大小范围相比,这绝对很小。而且由于软件的输入大小可能面临天文数字范围,因此算法的 Big O 复杂性(其基本的伸缩性)可能胜过任何实现细节。

考虑规范的排序示例。冒泡排序为 O(n 2 ),而合并排序为 O(n log n)。假设您有两个排序应用程序,使用气泡排序的应用程序 A 和使用合并排序的应用程序 B,假设输入大小约为 30 个元素,则应用程序 A 在排序时比应用程序 B 快 1000 倍。如果您不必排序多于 30 个元素,那么显然您应该首选应用程序 A,因为在这些输入大小下它要快得多。但是,如果您发现可能必须分类一千万个项目,那么您期望的是,在这种情况下,应用程序 B 实际上最终比应用程序 A 快数千倍,这完全是由于每种算法的扩展方式所致。

这是我在解释 Big-O 的常见变体时倾向于使用的简单的英语动物

在所有情况下,优先选择列表上方的算法而不是列表下方的算法。但是,转移到更昂贵的复杂性类别的成本差异很大。

O(1):

没有增长。不管问题有多大,您都可以在相同的时间内解决它。这有点类似于广播,无论广播范围内的人数多少,在给定距离上广播都需要消耗相同数量的能量。

O(log n ):

这种复杂性与O(1)相同,只不过差一点点。出于所有实际目的,您可以将其视为非常大的恒定比例。处理 1000 个项目和 10 亿个项目之间的工作差异只有六分之一。

O( n ):

解决问题的成本与问题的大小成正比。如果您的问题规模增加了一倍,那么解决方案的成本就会增加一倍。由于大多数问题都必须以某种方式扫描到计算机中,例如数据输入,磁盘读取或网络流量,因此通常这是一个负担得起的缩放因子。

O( n log n ):

这种复杂性与O( n非常相似。出于所有实际目的,两者是等效的。这种复杂程度通常仍被认为是可扩展的。通过调整假设,可以将某些O( n log n算法转换为O( n算法。例如,限制键的大小可减少从O( n log nO( n )的排序。

O( n 2 ):

生长为正方形,其中n是正方形边的长度。这与 “网络效应” 的增长率相同,在网络效应中,网络中的每个人都可能认识网络中的其他每个人。增长是昂贵的。如果不进行大量的体操练习,大多数可伸缩的解决方案就无法使用具有这种复杂性级别的算法。这通常也适用于所有其他多项式复杂度-O( n k -。

O(2 n ):

不缩放。您没有解决任何重要问题的希望。对于了解要避免的内容以及专家找到O( n k )中的近似算法很有用。

大 O 表示算法使用多少时间 / 空间(相对于其输入大小)。

如果算法为 O(n),则时间 / 空间将以与其输入相同的速率增加。

如果算法为 O(n 2 ),则时间 / 空间将以其输入平方的速率增加。

等等。