快速说明，我的回答几乎肯定会混淆Big Oh 表示法（这是一个上限）和 Big Theta 表示法“Θ”（这是一个两侧界限）。但根据我的经验，这实际上是非学术环境中的典型讨论。对于造成的任何混乱，我们深表歉意。

BigOh 复杂度可以用这个图来可视化：

我可以为 Big Oh 符号给出的最简单的定义是：

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

那句话中有一些重要的、故意选择的词：

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

阅读完其余部分后，请返回并重新阅读以上内容。

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

• 添加;
• 减法；
• 乘法; 和
• 分配。

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

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

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

看到图案了吗？的复杂性（即操作的次数）正比于数字数量Ñ在较大的数量。我们称之为O(n)或线性复杂度。

减法是类似的（除了您可能需要借入而不是进位）。

乘法不一样。您将数字排列起来，取底部数字中的第一个数字，然后将其依次乘以顶部数字中的每个数字，依此类推，直到每个数字。因此，要将两个 6 位数字相乘，我们必须进行 36 次乘法。我们可能需要进行多达 10 或 11 列添加才能获得最终结果。

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

当算法以 n- squared 进行缩放时，这是O(n 2 )或二次复杂度。现在是介绍另一个重要概念的好时机：

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

精明的人可能已经意识到我们可以将操作次数表示为：n 2 + 2n。但是正如您从我们的示例中看到的，每个数字都有两个百万位数字，第二项 (2n) 变得无关紧要（占该阶段总操作的 0.0002%）。

可以注意到，我们在这里假设了最坏的情况。在乘以6位数字时，如果其中一个有4位，另一个有6位，那么我们只有24次乘法。尽管如此，我们还是计算了那个“n”的最坏情况，即当两者都是 6 位数字时。因此，Big Oh 表示法是关于算法的最坏情况。

电话簿

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

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

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

这称为二分查找，无论您是否意识到，它每天都在编程中使用。

因此，如果您想在包含一百万个名字的电话簿中找到一个名字，您实际上最多可以通过执行此操作 20 次来找到任何名字。在比较搜索算法时，我们决定这个比较是我们的“n”。

• 对于 3 个姓名的电话簿，需要进行 2 次比较（最多）。
• 对于 7，最多需要 3。
• 对于 15，它需要 4。
• …
• 对于 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)；和
• 最坏情况：这也是 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

所以旅行商问题的 BigOh 是O(n!)或阶乘或组合复杂度。

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

有什么要考虑的。

多项式时间

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

O(n)、O(n 2 ) 等都是多项式时间。有些问题不能在多项式时间内解决。因此，世界上会使用某些东西。公钥密码学就是一个典型的例子。在计算上很难找到一个非常大的数的两个质因数。如果不是，我们就不能使用我们使用的公钥系统。

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