我更喜欢尽可能少的形式化定义和简单的数学。
快速提示，我的回答几乎肯定会引起困惑（大O符号）大O符号（这是一个上界）与BigTheta符号“Θ”（这是一个两侧界限）。但在我的经验中，这实际上在非学术环境中的讨论中是很典型的。对此造成的任何困惑表示歉意。
大O复杂度可以用这个图来可视化：
[或对数复杂度。现在，我们讨论的对数可以是自然对数（底数为e）、对数10、对数2或其他基数。没关系，它仍然是O(log n)，就像O(2n2)和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个城镇时，宇宙中没有足够的时间用传统计算机解决该问题。”
值得思考。
多项式时间
我想快速提及的另一个点是，任何具有O(na)复杂度的算法都被称为具有多项式复杂度或可以在多项式时间内解决。
O(n)、O(n^2)等都是多项式时间。有些问题无法在多项式时间内解决。世界上某些事情就是基于这个原因而存在的。[公钥加密]是一个典型的例子。在非常大的数字中找到两个质因数是非常计算密集的。如果不是这样，我们就无法使用我们现在使用的公钥系统。
无论如何，这就是我对（希望是简单的英语）BigOh（修订版）的解释。
标签：解释,电话号码,符号,复杂度,名字,英文,情况,电话簿,我们 From： https://www.cnblogs.com/xiaomandujia/p/17755678.html