内容来自 DOC https://q.houxu6.top/?s=什么是“大O”符号的简单英文解释？

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

快速提示，我的回答几乎肯定会引起困惑（大O符号）大O符号（这是一个上界）与BigTheta符号“Θ”（这是一个两侧界限）。但在我的经验中，这实际上在非学术环境中的讨论中是很典型的。对此造成的任何困惑表示歉意。

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

[![Big Oh Analysis](https://i.stack.imgur.com
你可以注意到，我们在这里假设了最坏的情况。当我们在乘6位数的数字时，如果其中一个是4位数，另一个是6位数，那么我们只有24次乘法。然而，我们计算的是'n'的最坏情况，即当两个都是6位数时。因此，Big Oh表示法是关于算法的最坏情况。

电话簿

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

现在，如果你要指导计算机在包含100万个名字的电话簿中查找“John Smith”的电话号码，你会怎么做？忽略你无法猜测“S”开始了多少的事实（让我们假设你不能），你会怎么做？

一个典型的实现可能是打开中间，取第50万份并将其与“Smith”进行比较。如果它恰好是“Smith, John”，那么我们真的很幸运。更有可能的是“John Smith”会在那个名字之前或之后。如果是后者，我们将电话簿的前半部分再分成两半并重复。如果是前者，我们将电话簿的后半部分再分成两半并重复。以此类推。

这就是所谓的二分查找，它在编程中每天都在使用，无论你是否意识到。

所以，如果你想在一本有一百万个名字的电话簿中找到任何一个名字，你实际上可以通过这样做最多20次来找到。在比较搜索算法时，我们决定将这个比较作为我们的'n'。

对于3个名字的电话簿，需要2次比较（最多）。

对于7个名字，最多需要3次。

对于15个名字，需要4次。

…

对于100万个名字，需要20次。

这是不是令人震惊地好？

从Big Oh的角度来看，这是O(log n)或对数复杂度。现在，我们讨论的对数可以是自然对数（底数为e）、对数10、对数2或其他基数。没关系，它仍然是O(log n)，就像O(2n^2)和O(100n2)仍然都是O(n^2)一样。

在这一点上，有必要解释一下Big Oh可以用来确定算法的三种情况：

最佳情况：在电话簿搜索中，最好的情况是我们一次就找到了名字。这是O(1)或常数复杂度；

预期情况：如上所述，这是O(log n)；以及

最坏情况：这也是O(log n)。

通常情况下，我们不关心最佳情况。我们对预期和最坏情况感兴趣。有时，这些中的一个或另一个可能更重要。

回到电话簿。

如果你有一个电话号码并想找到一个名字呢？警察有一个反向电话簿，但是这样的查找是被公众拒绝的。或者它们被拒绝了吗？技术上，你可以在普通的电话簿中反向查找一个号码。怎么做？

你从名字开始，然后比较号码。如果匹配，那就太好了，如果不匹配，你就继续下一个。你必须这样做，因为电话簿是无序的（至少按电话号码来说）。

因此，要在给定电话号码（反向查找）的情况下找到一个人的名字：

最佳情况：O(1)；

预期情况：O(n)（对于50万个）；以及

最坏情况：O(n)（对于100万个）。

实际上，数量要少于这个，因为其中一些是等价的（例如，A→B→C和C→B→A是等价的，因为它们使用相同的道路，只是顺序相反）。

实际上，有三种可能性。

将此问题扩展到4个城镇，您将有（根据记忆）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

因此，旅行商问题的BigOh为O(n!)或阶乘或组合复杂度。

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

值得思考。