“Big O”符号的简单解释是什么？

獨夫之心

我更喜欢尽可能少的正式定义和简单的数学。
1 g" [8 c+ M- R, L3 c' v                                                               
) u* D8 l# {+ F    解决方案:                                                               
6 |$ e: L0 D% N1 y) b5 Y) ^                                                                快速解释，我的回答几乎肯定会混淆Big Oh 表示法（这是一个上限）和 Big Theta 表示法“Θ(这是两边的边界)。但根据我的经验，这实际上是非学术环境中的典型讨论。我们为任何混乱道歉。
* `; e* p* T" g) [! k; \BigOh 复杂度可以用这张图来可视化:

我可以为 Big Oh 符号最简单的定义是：
Big Oh 表示法是算法复杂性的相对表示。
% b3 A% i: D2 g) t$ U1 y0 ?+ ?. ^9 s这句话有一些重要的、故意的词：
$ A1 _& w- {6 ~3 I- p相对：你只能比较苹果和苹果。您无法将算术乘法算法与排序整数列表的算法进行比较。但比较两种算法（一种乘法，一种加法）会告诉你一些有意义的事情；
表示：    BigOh（以最简单的形式）将算法之间的比较减少到单个变量。变量是根据观察或假设选择的。例如，排序算法通常基于比较操作（比较两个节点以确定它们的相对顺序）进行比较。这个假设更贵。但如果它更便宜，但交换很贵呢？它改变了比较；和
0 @  g$ r. J) ^, y7 k6 [) d复杂性：如果我需要一秒钟来排序 10000 元素，我需要多长时间来排序100万元素？在这种情况下，复杂性是对其他事物的相对衡量。阅读其余部分后，请返回并重新阅读上述内容。
' P$ z5 r" T3 r; Y，我能想到的BigOh 最好的例子是算术。取两个数字(123456 和 789012)。我们在学校学到的基本算术是:
添加;
3 Y' I8 W# s, p2 R" `" [减法；
乘法; 和
分配。每一个都是一个操作或一个问题。解决这些问题的方法称为算法。
加法是最简单的。您将数字排列成一行（向右），并在列中添加数字，并将添加的最后一个数字写入结果中。数字的十位部分将转移到下一列。
让我们假设这些数字的相加是这个算法中最昂贵的操作。按理说，要将这两个数字相加，我们必须将 6 位数字相加（并且可能带有第 7 位）。如果我们将两个 100 位数字相加，我们必须进行 100 次加法。如果我们将两个10000 位数加，我们必须进行 10000 次加法。
4 J" P9 [; [# i/ O看图案了吗？复杂性(即操作次数)与数字数量成正比?数量大。我们称之为O(n)或线性复杂度。
6 f5 [) m/ g, S减法是相似的(除了你可能需要借入而不是进入)。
乘法不同。您将数字排列在底部数字中的第一个数字中，然后将其乘以顶部数字中的每个数字，等等，直到每个数字。因此，为了乘以两个 6 位数，我们必须乘以 36 次数。我们可能需要添加多达 10 或 11 列来获得最终结果。
如果我们有两个 100 位数，我们需要做 1000 次乘法和 200 次加法。对于两个100万位数，我们需要做1万亿次乘法和200万次加法。
7 w: e1 d% L3 q4 R$ G) W9 ~当算法以 n- squared 进行缩放时，这是O(n 2 )或二次复杂度。现在是介绍另一个重要概念的好时机：
我们只关心复杂性中最重要的部分。
聪明的人可能已经意识到，我们可以将操作次数表示为：n 2   2n。但正如你从我们的例子中看到的，每个数字有两百万位数字，第二项 (2)n) 变得无关紧要(现阶段总操作的 0.0002%）。
; t) C8 r/ M/ m+ j& ?" n可以注意到，我们在这里假设了最糟糕的情况。乘以六位数时，如果其中一个有四个，另一个有六个，我们只能乘以24次。尽管如此，我们还是计算了n最坏的情况是，当两者都是 6 位数时。Big Oh 表示法是关于算法的最坏情况。
5 U' n1 W) }$ m& u0 o电话簿我能想到的下一个最好的例子是电话簿，通常被称为白页或类似的名字，但因国家/地区而异。但我说的是根据姓氏，然后是名称的第一个字母或名称，可能是地址，然后是电话号码列出人员。
现在，如果你让电脑在电话簿上搜索 1,000,000 的名字，John Smith你会怎么做？忽略你可以猜测 S 你会怎么做？
0 u* y; j) C1 M9 C# q1 e" `! `# a; |% [一个典型的实现可能是打开中间，拿第 5万次，和史密斯比较。如果碰巧是史密斯，约翰，我们真的很幸运。更有可能是John Smith它将出现在名称之前或之后。如果是在我们之后，将电话簿的后半部分分成两半并重复。如果在此之前，我们将电话簿的前半部分分成两半并重复。
这称为二分查找，不管你是否意识到它每天都在编程中使用。
6 t9 c, s8 V# @& D因此，如果您想在包含一百万个名字的电话簿中找到一个名字，您实际上最多可以通过执行此操作 20 次来找到任何名字。在比较搜索算法时，我们决定这个比较是我们的“n”。
3 名称的电话簿需要 2 次比较(最多)。
: y1 [0 J3 l+ ]# i, y0 Q7最多需要 3。
15需要 4。
0 @9 \1 H* Q/ s& j8 q( D+ g  Q…
1,000,000，需要 20。真的很棒，不是吗？
在 BigOh 术语中，这是O(log n)或对数复杂度。现在讨论的对数可能是 ln（以 e 为底）、log 10、log 2或其他一些底数。没关系仍然是 O(log n) 就像 O(2n 2 ) 和 O(100n 2 ) 仍然是 O(n 2 )。
这一点有必要解释 BigOh 可用于通过算法确定三种情况：
最佳情况：在电话簿搜索中，最好的情况是我们在一次比较中找到名字。这是O(1)或常数复杂度；
预期情况：如上所述，这是 O(log n)；和
2 U+ @9 `2 s  L1 a最坏情况：这也是 O(log n)。我们通常不关心最好的情况。我们对预期和最坏的情况感兴趣。有时候，其中一个会更重要。
回电话簿。
如果你有电话号码，想找到你的名字怎么办？警方有反向电话簿，但公众拒绝进行此类调查。还是他们？从技术上讲，你可以在普通电话簿电话簿中的号码。怎么样？
你从名字开始，比较数字。如果这是一场比赛，很好，如果不是，你会继续下一场比赛。你必须这样做，因为电话簿是无序的（无论如何都是按电话号码）。
因此，要找到给定电话号码的名称(反向搜索):
* V* K# l7 d2 i6 Q$ u9 t, w最佳情况：    O(1)；
预期案例：    O(n)(对 500,000)
最坏情况：    O(n)( 1,000,000)。旅行推销员这是计算机科学中一个相当有名的问题，值得一提。在这个问题上，你有 N 一个城镇。这些城镇中的每城镇都通过一定距离的道路连接到一个或多个其他城镇。旅行者的问题是找到每个城镇最短的旅行。
听起来很简单？再想想。
- v; F( i: |, Z0 x- Y/ p如果你有 3个城镇A、B 和 C，所有城镇之间都有道路，所以你可以：
A → B → C
) q6 M! o+ l9 |' U5 rA → C → B
B→C→A
5 K" z1 W% l, lB → A → C
5 T- f2 @* ]* m5 GC → A → B
( c  O: @& |) O4 ~9 ]- iC → B → A嗯，其实比这少，因为有些是等效的(比如，A → B → C 和 C → B → A 是等效的，因为它们使用相同的道路，只是相反的)。
6 A4 s  G7 b3 ?/ l! |事实上，有三种可能性。
# `2 m* ^) U/ a" ~把它带到 4个城镇，你就会有 (iirc) 12 可能性。
5 是 60。
6 变成 360。这是称为阶乘数学运算函数。
- t' S6 \3 k( Y) s5！= 5 × 4 × 3 × 2 × 1 = 120
6！= 6 × 5 × 4 × 3 × 2 × 1 = 720
7！= 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
' F/ E# `9 M3 g" O) n…
25！= 25 × 24 × … × 2 × 1 = 15、511、210、043、985、984、000
7 `3 D7 |5 O4 J1 Y( D5 [" {/ K…
50！= 50 × 49 × … × 2 × 1 = 3.04140932 × 10 64所以旅行者问题 BigOh 是O(n!)或复杂性的阶乘或组合。
当你到达 200个城镇时，宇宙中没有足够的时间来解决传统计算机的问题。
) N% r2 Z- ^5 a/ r考虑什么？
多项式时间我想快速提及的另一点是，任何具有O(n a )复杂算法被称为具有复杂性的算法多项复杂度或可在多项式时间内求解。
O(n)、O(n 2 ) 等都是多项式时间。有些问题不能在多项式时间内解决。因此，世界上会使用一些东西。公钥密码学就是一个典型的例子。在计算中很难找到一个非常大的两个质量因素。如果没有，我们就不能使用我们使用的公钥系统。
" y! T, X, T: s无论如何，这就是我对 BigOh(修订版)解释(希望是简单的英语)。