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


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


4533
2018-01-28 11:10


起源


摘要:算法复杂性的上限。另见类似问题 大O,你如何计算/近似它? 为了一个很好的解释。 - Kosi2801
其他答案非常好,只需要理解一个细节:O(log n)或类似的方法,它取决于输入的“长度”或“大小”,而不是值本身。这可能很难理解,但非常重要。例如,当您的算法在每次迭代中将事物分成两部分时,就会发生这种情况。 - Harald Schilly
在麻省理工学院“计算机科学与编程入门”课程的第8讲中,有一个专门讨论算法复杂性的讲座 youtube.com/watch?v=ewd7Lf2dr5Q 它不是完全简单的英语,但可以通过易于理解的示例给出很好的解释。 - ivanjovanovic
Big O是假设算法将执行最大迭代次数的函数的最坏情况性能的估计。 - Paul Sweatte
Big-O notation explained by a self-taught programmer - Soner Gönül


答案:


快速说明,这几乎肯定令人困惑 大O符号 (带有Theta表示法的上限)(这是一个双边界)。根据我的经验,这实际上是非学术环境中的典型讨论。对所引起的任何混乱道歉。


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

Big O Analysis

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

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

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

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

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

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

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

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

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

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

看模式?该 复杂 (作为操作次数)与位数成正比 ñ 在更大的数字。我们称之为 上) 要么 线性复杂性

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

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

如果我们有两个100位数字,我们需要进行10,000次乘法和200次加法。对于两百万个数字,我们需要做一万亿(1012)乘法和200万增加。

随着算法与n-缩放平方, 这是 2 要么 二次复杂度。这是介绍另一个重要概念的好时机:

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

精明的人可能已经意识到我们可以将操作次数表示为:n2 + 2n。但正如你从我们的例子中看到的那样,每个数字有两个数字,第二个术语(2n)变得微不足道(占该阶段总操作的0.0002%)。

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

电话簿

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

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

一个典型的实现可能是打开到中间,取500,000 并将其与“史密斯”进行比较。如果碰巧是“史密斯,约翰”,我们真的很幸运。更有可能的是“约翰史密斯”将在该名称之前或之后。如果是在我们之后,我们将电话簿的后半部分分成两半并重复。如果是在那之前,我们将电话簿的前半部分分成两半并重复。等等。

这被称为a 二分搜索 无论你是否意识到,它每天都在编程中使用。

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

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

那是惊人的好不是吗?

在Big-O术语中,这是 O(log n) 要么 对数复杂度。现在所讨论的对数可以是ln(基数e),log10,日志2 或其他一些基础。没关系,它仍然是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是等价的,因为它们使用相同的道路,只是相反)。

实际上有3种可能性。

  • 把它带到4个城镇,你有(iirc)12种可能性。
  • 5分是60分。
  • 6变为360。

这是一个称为a的数学运算的函数 阶乘。基本上:

  • 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是 上!) 要么 阶乘或组合复杂性

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

需要考虑的事情。

多项式时间

我想要快速提及的另一点是任何具有复杂性的算法 一个 据说有 多项式复杂性 或者是可以解决的 多项式时间

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

无论如何,这是我(希望简单英语)对Big O(修订版)的解释。


6094
2018-01-28 11:18



而其他答案则侧重于解释O(1),O(n ^ 2)等人之间的差异....你的问题是详细说明如何将算法分类为n ^ 2,nlog(n)等。+ 1是一个很好的答案,帮助我理解Big O符号 - Yew Long
一个人可能想要补充一点,大O代表一个上限(由算法给出),big-Omega给出一个下限(通常作为独立于特定算法的证明)和big-Theta意味着一个“最优”算法达到那个下限是众所周知的。 - mdm
如果您正在寻找最长的答案,这是很好的,但不是以最简单的方式解释Big-O的答案。 - kirk.burleson
-1:这是明显错误的:_“BigOh是算法复杂性的相对表示”。不,BigOh是一个渐近的上界,并且很好地独立于计算机科学。 O(n)是线性的。不,你把BigOh与theta混淆了。 log n是O(n)。 1是O(n)。这个答案(以及评论)的赞成数量,这使得将Theta与BigOh混淆的基本错误令人非常尴尬......
“当你到达200个城镇时,宇宙中没有足够的时间来解决传统计算机的问题。” 当宇宙即将结束? - Isaac


它显示了算法如何扩展。

2: 作为。。而被知道 二次复杂性

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

请注意,项目数增加了10倍,但时间增加了10倍2。基本上,n = 10,因此O(n2)给出了缩放因子n2 这是102

上): 作为。。而被知道 线性复杂性

  • 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 或者他们说的是什么,但这将是缩放的主要因素。


662
2018-01-28 11:28



这个定义到底意味着什么? (项目数仍然增加10倍,但O(1)的比例因子始终为1.) - HollerTrain
不是秒,操作。此外,你错过了阶乘和对数时间。 - Chris Charabaruk
这并不能很好地解释O(n ^ 2)可能正在描述一个精确运行的算法.01 * n ^ 2 + 999999 * n + 999999.重要的是要知道算法是用这个比例进行比较的,那个当n'足够大'时,比较有效。 Python的timsort实际上对小型数组使用插入排序(最差/平均情况O(n ^ 2)),因为它的开销很小。 - Darthfett
这个答案也混淆了大O符号和Theta符号。 n的所有输入(通常简写为1)返回1的函数实际上是O(n ^ 2)(即使它也在O(1)中)。类似地,仅需要执行花费恒定时间量的一个步骤的算法也被认为是O(1)算法,但也被认为是O(n)和O(n ^ 2)算法。但也许数学家和计算机科学家不同意这个定义: - /。 - Jacob Akkerboom
在这个答案中考虑的O(log n)对数复杂度是基数10.通常标准是用基数2计算。应该记住这个事实,不应该混淆。同样如@ChrisCharabaruk所述,复杂性表示操作次数而不是秒。 - Aksh1801


Big-O表示法(也称为“渐近增长”表示法)是 当你忽略原点附近的常数因子和东西时,什么功能“看起来像”。我们用它来谈谈 事情如何规模


基本

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

  • f(x) ∈ O(upperbound) 手段 f “增长不快” 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但重要的是它“像”一样“
  • 概率预期将某些病毒式营销视为时间函数的人数
  • 网站延迟如何随CPU或GPU或计算机集群中的处理单元数量而变化
  • CPU上的热量输出如何随晶体管数量,电压等而变化。
  • 作为输入大小的函数,算法需要运行多长时间
  • 作为输入大小的函数,算法需要运行多少空间

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

备份一点:握手的数量恰好是n-choose-2或 N*(N-1)/2 (N个人中的每个人都握着N-1其他人的手,但是这个双手握手因此除以2):

everyone handshakes everyone else. Image credit and license per wikipedia/wikimedia commons "complete graph" article.  adjacency matrix

但是,对于非常多的人来说,线性项 N 相形见绌并且有效地贡献了0(在图表中:随着参与者数量变大,对角线上空盒子的比例随总箱数变小)。因此缩放行为是 order N²,或握手的数量“像N²一样增长”。

#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²这么多,如果我们要记下比例#handshakes /x²,我们不需要这个事实 究竟 x²握手甚至不会在十进制中显示任意大的时间。

例如对于x = 1百万,比率#handshakes /x²:0.499999 ...


建立直觉

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

“对于足够大的输入= N,无论常数因素如何,如果我  输入大小


362
2017-07-08 04:46



一个很好的数学答案,但OP要求一个简单的英语答案。这种水平的数学描述不是理解答案所必需的,尽管对于特别注重数学的人而言,理解它可能比“普通英语”简单得多。然而,OP要求后者。 - El Zorko
据推测,OP以外的人可能会对这个问题的答案感兴趣。这不是网站的指导原则吗? - Casey
虽然我可以看到为什么人们会撇开我的答案,并认为它太肮脏(特别是“数学是新的普通英语”讽刺言论,自从删除),原始问题询问关于函数的大O,所以我试图明确地以一种补充普通英语直觉的方式谈论功能。这里的数学经常可以被掩盖,或者用高中数学背景来理解。我觉得人们可能会在最后看到数学附录,并认为这是答案的一部分,当它只是在那里看到什么 真实 数学看起来像。 - ninjagecko
这是一个很棒的答案; IMO比投票最多的IMO要好得多。所需的“数学”不会超出理解“O”后括号中的表达式所需要的,没有使用任何示例的合理解释可以避免。 - Dave Abrahams
“f(x)∈O(上限)意味着f”增长不快于“上限”这三个简单的措辞,但数学上对大哦,Theta和Omega的正确解释是金色的。他用简单的英语向我描述了在没有编写复杂的数学表达式的情况下,5个不同来源似乎无法转化为我的观点。谢啦! :) - timbram


编辑:快速说明,这几乎肯定令人困惑 大O符号 (带有Theta符号的上限)(上限和下限)。根据我的经验,这实际上是非学术环境中的典型讨论。对所引起的任何混乱道歉。

用一句话说:随着工作规模的增加,完成工作需要多长时间?

显然,只使用“大小”作为输入,“时间”作为输出 - 如果你想谈论内存使用等,同样的想法也适用。

这是一个我们想要干的N T恤的例子。好 承担 让它们处于干燥位置非常快(即人类的相互作用可以忽略不计)。当然,现实情况并非如此......

  • 在外面使用清洗线:假设你有一个无限大的后院,洗涤在O(1)时间内干燥。无论你有多少,它都会得到相同的阳光和新鲜空气,因此尺寸不会影响干燥时间。

  • 使用滚筒式烘干机:每次装入10件衬衫,然后一小时后完成。 (忽略这里的实际数字 - 它们无关紧要。)所以干掉50件衬衫需要 关于 干燥10件衬衫的5倍。

  • 将所有东西放在一个通风橱中:如果我们将所有东西放在一个大堆中,只是让一般的温暖,它将需要很长时间让中间衬衫变干。我不想猜测细节,但我怀疑这至少是O(N ^ 2) - 随着你增加洗涤负荷,干燥时间增加得更快。

“大O”符号的一个重要方面是它  说哪个算法对于给定的大小会更快。获取哈希表(字符串键,整数值)与对数组(字符串,整数)。基于字符串,在哈希表或数组中的元素中查找键是否更快? (即对于数组,“找到字符串部分与给定键匹配的第一个元素。”)哈希表通常是摊销的(〜=“平均”)O(1) - 一旦它们被设置,它应该采取同时在100条目表中查找条目,如在1,000,000条目表中。在数组中查找元素(基于内容而不是索引)是线性的,即O(N) - 平均而言,您将不得不查看一半条目。

这是否使哈希表比查找数组更快?不必要。如果你有一个非常小的条目集合,一个数组可能会更快 - 你可以在计算你正在查看的哈希码的时间内检查所有字符串。然而,随着数据集变大,哈希表最终会击败数组。


237
2018-01-28 11:16



哈希表需要运行算法来计算实际数组的索引(取决于实现)。数组只有O(1),因为它只是一个地址。但这与问题无关,只是一个观察:) - Filip Ekberg
jon的解释对我认为的问题非常重要。这正是一个人可以向某个妈妈解释它的方式,她最终会理解它我认为:)我喜欢衣服的例子(特别是最后一个,它解释了复杂性的指数增长) - Johannes Schaub - litb
Filip:我不是在谈论通过索引来解决数组,我在谈论在数组中找到匹配的条目。你能重新阅读答案,看看是否仍然不清楚? - Jon Skeet
@Filip Ekberg我想你正在考虑一个直接地址表,其中每个索引直接映射到一个键,因此是O(1),但是我相信Jon正在谈论一个未排序的键/值对数组,你必须搜索通过线性。 - ljs
@RBT:不,这不是二元查找。它可以得到正确的哈希 桶 立即,只是基于从哈希码到桶索引的转换。之后,在存储桶中找到正确的哈希码可能是线性的,也可能是二进制搜索...但到那时你只需要字典总大小的一小部分。 - Jon Skeet


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

例子:

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

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

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

  • O(2ñ):如果输入大小增加1,则运行时间加倍

输入大小通常是表示输入所需的位数。


120
2018-01-28 11:23



不正确!例如O(n):如果我将输入大小加倍,运行时将乘以有限的非零常数。我的意思是O(n)= O(n + n) - arena-ru
我在谈论f(n)= O(g(n))中的f,而不是你似乎理解的g。 - starblue
我赞成,但最后一句话对我的贡献不大。在讨论或测量Big(O)时,我们不经常谈论“位”。 - cdiggins
您应该为O(n log n)添加一个示例。 - Christoffer Hammarström
这不是那么清楚,基本上它的表现比O(n)差一点。因此,如果n加倍,则运行时间乘以稍大于2的因子。 - starblue


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

Big O可用于比较两种算法随着输入数量的增加而扩展的程度。

更确切地说 大O符号 用于表示函数的渐近行为。这意味着函数在接近无穷大时的行为方式。

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

  • O(1)  - 无论输入集的大小如何,完成时间都是相同的。一个例子是通过索引访问数组元素。
  • O(Log N)  - 完成时间大致与log2(n)一致。例如,1024个项目大约需要32个项目的两倍,因为Log2(1024)= 10而Log2(32)= 5.一个例子是查找一个项目 二叉搜索树 (BST)。
  • 上)  - 完成时间与输入集的大小成线性比例。换句话说,如果您将输入集中的项目数加倍,则算法大约需要两倍的时间。一个例子是计算链表中的项目数。
  • O(N Log N)  - 完成时间增加项目数乘以Log2(N)的结果。一个例子是 堆排序 和 快速排序
  • O(N ^ 2)  - 完成时间大致等于项目数的平方。一个例子是 泡泡排序
  • 上!)  - 完成时间是输入集的阶乘。这方面的一个例子是 旅行推销员问题蛮力解决方案

当输入大小朝向无穷大增加时,大O忽略了对函数的增长曲线没有有意义贡献的因素。这意味着简单地忽略了添加到函数或乘以函数的常量。


97
2017-09-05 16:31



cdiggins,如果我有O(N / 2)复杂度,应该是O(N)还是O(N / 2),例如,如果我将循环超过半字符串的复杂性。 - Melad Ezzat
@Melad这是一个常数(0.5)与函数相乘的例子。这被忽略,因为它被认为对非常大的N值具有有意义的影响。 - cdiggins


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

你可能经常看到O(n),O(n2),O(nlogn)等等,所有这些只是展示的方式;算法如何改变?

O(n)意味着大O是n,现在你可能会想,“什么是n!?” “n”是元素的数量。想要在阵列中搜索项目的图像。您必须查看每个元素并将其视为“您是正确的元素/项目吗?”在最坏的情况下,该项目位于最后一个索引,这意味着它花费的时间与列表中的项目一样多,因此为了通用,我们说“哦,嘿,n是一个公平的给定数量的值!” 。

那么你可能会理解“n2“意思是,但更具体地说,你会想到你有一个简单,最简单的排序算法; bubblesort。这个算法需要查看每个项目的整个列表。

我的列表

  1. 1
  2. 6
  3. 3

这里的流程将是:

  • 比较1和6,哪个最大? Ok 6处于正确的位置,向前迈进!
  • 比较6和3,哦,3更少!让我们移动一下,好的清单改变了,我们需要从现在开始!

这是哦2 因为,你需要查看列表中的所有项目都有“n”项。对于每个项目,您再次查看所有项目,为了进行比较,这也是“n”,因此对于每个项目,您看起来是“n”次,意味着n * n = n2

我希望这就像你想要的一样简单。

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


77
2018-01-28 11:14



对于logN,我们考虑从0到N / 2的循环运行O(log log N)?我的意思是程序是怎么样的?请原谅我纯粹的数学技能 - Pablo Escobar


Big O描述了算法的基本缩放特性。

Big O没有告诉你有关给定算法的大量信息。它切入骨骼并仅提供有关算法的缩放特性的信息,特别是算法的资源使用(思考时间或内存)如何根据“输入大小”进行缩放。

考虑蒸汽机和火箭之间的区别。它们不仅仅是同一种物品的不同品种(例如,普锐斯发动机与兰博基尼发动机),但它们的核心是不同类型的推进系统。蒸汽机可能比玩具火箭更快,但没有蒸汽活塞发动机能够达到轨道运载火箭的速度。这是因为这些系统在达到给定速度(“输入尺寸”)所需的燃料关系(“资源使用”)方面具有不同的缩放特性。

为什么这个这么重要?因为软件处理的问题可能因数据大小不同而有所不同。考虑一下。前往月球所需的速度与人类步行速度之间的比率小于10,000:1,与软件可能面临的输入尺寸范围相比,这个比例非常小。而且由于软件可能面临输入大小的天文范围,因此算法的Big O复杂性可能会超越任何实现细节,这是基本的扩展性质。

考虑规范排序示例。冒泡排序是O(n2)merge-sort是O(n log n)。假设您有两个排序应用程序,即使用冒泡排序的应用程序A和使用合并排序的应用程序B,并且假设对于大约30个元素的输入大小,应用程序A在排序时比应用程序B快1,000倍。如果您不必排序超过30个元素,那么您应该更喜欢应用程序A,因为它在这些输入大小上要快得多。但是,如果您发现可能需要对1000万个项目进行排序,那么您所期望的是,在这种情况下,应用程序B实际上最终比应用程序A快数千倍,这完全取决于每种算法的扩展方式。


52
2018-01-28 13:12





这是我在解释Big-O的常见变种时倾向于使用的普通英语动物

在所有情况下,首选列表中较高的算法列表中较低的算法。但是,迁移到更昂贵的复杂性类别的成本差别很大。

O(1):

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

O(日志 ñ):

这种复杂性与之相同 O(1) 除了它只是有点糟糕。出于所有实际目的,您可以将其视为非常大的常量缩放。处理1千到10亿件物品之间的工作差异只是因素六。

O(ñ):

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

O(ñ 日志 ñ):

这种复杂性非常类似于 O(ñ。出于所有实际目的,两者是等价的。这种复杂程度通常仍被认为是可扩展的。通过调整一些假设 O(ñ 日志 ñ 算法可以转化为 O(ñ 算法。例如,限制键的大小会减少排序 O(ñ 日志 ñ 至 O(ñ

O(ñ2):

成长为一个广场,在哪里 ñ 是正方形边长。这与“网络效应”的增长速度相同,网络中的每个人都可能知道网络中的其他人。增长是昂贵的。大多数可扩展的解决方案无法使用具有这种复杂程度的算法,而无需进行重要的体操。这通常适用于所有其他多项式复杂性 - O(ñķ  - 以及。

O(2ñ):

不规模。你没有希望解决任何非平凡的问题。有助于知道要避免什么,以及专家找到的近似算法 O(ñķ


35
2018-01-27 23:09



你能否考虑一下O(1)的另一个类比?我的工程师想要讨论由于障碍物造成的射频阻抗。 - johnwbyrd
我确实使用了“有点”这个词。 - Andrew Prock