algorithm - 什么是 "Big O"符号的简单英文解释？

Question

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

Answer 1

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

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

我可以为 Big Oh 符号给出的最简单的定义是:
Big Oh 符号是算法复杂性的相对表示。
这句话中有一些重要的、故意选择的词:

• relative: you can only compare apples to apples. You can't compare an algorithm that does arithmetic multiplication to an algorithm that sorts a list of integers. But a comparison of two algorithms to do arithmetic operations (one multiplication, one addition) will tell you something meaningful;
• representation: BigOh (in its simplest form) reduces the comparison between algorithms to a single variable. That variable is chosen based on observations or assumptions. For example, sorting algorithms are typically compared based on comparison operations (comparing two nodes to determine their relative ordering). This assumes that comparison is expensive. But what if the comparison is cheap but swapping is expensive? It changes the comparison; and
• complexity: if it takes me one second to sort 10,000 elements, how long will it take me to sort one million? Complexity in this instance is a relative measure to something else.

阅读完其余部分后，请返回并重新阅读以上内容。
我能想到的 BigOh 最好的例子就是做算术。取两个数字(123456 和 789012)。我们在学校学到的基本算术运算是:

• addition;
• subtraction;
• multiplication; and
• division.

每一个都是一个操作或一个问题。解决这些问题的方法称为 算法 。
加法是最简单的。您将数字对齐(向右)并在列中添加数字，并在结果中写入该添加的最后一个数字。该数字的“十位”部分将转移到下一列。
让我们假设这些数字的相加是这个算法中最昂贵的操作。按理说，要将这两个数字相加，我们必须将 6 位数字相加(并且可能带有第 7 位)。如果我们将两个 100 位数字相加，我们必须进行 100 次加法。如果我们将 两个 10,000 位数字相加，我们必须进行 10,000 次加法。
看到图案了吗？ 复杂度 (即运算次数)与较大数字中的位数 n 成正比。我们将此称为 O(n) 或 线性复杂度 。
减法是类似的(除了您可能需要借入而不是进位)。
乘法不一样。您将数字排列起来，取底部数字中的第一个数字，然后依次乘以顶部数字中的每个数字，依此类推，直到每个数字。因此，要将两个 6 位数字相乘，我们必须进行 36 次乘法。我们可能需要进行多达 10 或 11 列添加才能获得最终结果。
如果我们有两个 100 位数字，我们需要做 10,000 次乘法和 200 次加法。对于两个百万位数的数字，我们需要做一万亿(1012)次乘法和两百万次加法。
随着算法以 n 平方进行缩放，这是 O(n2) 或 二次复杂度 。现在是介绍另一个重要概念的好时机:
我们只关心复杂性中最重要的部分。
精明的人可能已经意识到我们可以将操作次数表示为:n2 + 2n。但是正如您从我们的示例中看到的，每个数字都有两个百万位数字，第二项 (2n) 变得无关紧要(占该阶段总操作的 0.0002%)。
可以注意到，我们在这里假设了最坏的情况。在乘以6位数字时，如果其中一个有4位，另一个有6位，那么我们只有24次乘法。尽管如此，我们还是计算了那个“n”的最坏情况，即当两者都是 6 位数字时。因此，Big Oh 表示法是关于算法的最坏情况。
电话簿
我能想到的下一个最好的例子是电话簿，通常称为白页或类似名称，但因国家/地区而异。但我说的是按姓氏，然后是姓名首字母或名字，可能是地址，然后是电话号码来列出人员。
现在，如果您要让计算机在包含 1,000,000 个姓名的电话簿中查找“John Smith”的电话号码，您会怎么做？忽略您可以猜测 S 开始多远的事实(假设您不能)，您会怎么做？
典型的实现可能是打开中间位置，取第 500,000 个并将其与“史密斯”进行比较。如果碰巧是“史密斯，约翰”，我们真的很幸运。更有可能的是“John Smith”将出现在该名称之前或之后。如果是在我们之后，然后将电话簿的后半部分分成两半并重复。如果在此之前，我们将电话簿的前半部分分成两半并重复。等等。
这称为 二进制搜索 ，无论您是否意识到，它每天都在编程中使用。
因此，如果您想在包含一百万个名字的电话簿中找到一个名字，您实际上最多可以通过执行此操作 20 次来找到任何名字。在比较搜索算法时，我们决定这种比较是我们的“n”。

• For a phone book of 3 names it takes 2 comparisons (at most).
• For 7 it takes at most 3.
• For 15 it takes 4.
• …
• For 1,000,000 it takes 20.

这真是太好了，不是吗？
在 BigOh 术语中，这是 O(log n) 或 对数复杂度 。现在所讨论的对数可能是 ln(以 e 为底)、log10、log2 或其他一些底数。没关系它仍然是 O(log n) 就像 O(2n2) 和 O(100n2) 仍然都是 O(n2)。
在这一点上有必要解释一下 BigOh 可用于通过算法确定三种情况:

• Best Case: In the telephone book search, the best case is that we find the name in one comparison. This is O(1) or constant complexity;
• Expected Case: As discussed above this is O(log n); and
• Worst Case: This is also O(log n).

通常我们不关心最好的情况。我们对预期和最坏情况感兴趣。有时，其中之一会更重要。
回到电话簿。
如果您有电话号码并想查找姓名怎么办？警方有一个反向电话簿，但一般公众拒绝进行此类查询。还是他们？从技术上讲，您可以反向查找普通电话簿中的号码。如何？
您从名字开始并比较数字。如果这是一场比赛，很好，如果不是，你继续下一场。你必须这样做，因为电话簿是 无序 (无论如何都是电话号码)。
因此，要查找给定电话号码的名称(反向查找):

• Best Case: O(1);
• Expected Case: O(n) (for 500,000); and
• Worst Case: O(n) (for 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种可能。

• Take this to 4 towns and you have (iirc) 12 possibilities.
• With 5 it's 60.
• 6 becomes 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⁶⁴

所以旅行商问题的 BigOh 是 O(n!) 或 阶乘或组合复杂度 。
当你到达 200 个城镇时，宇宙中已经没有足够的时间来解决传统计算机的问题了。
有什么要考虑的。
多项式时间
我想快速提及的另一点是，任何复杂度为 O(na) 的算法都被称为具有 多项式复杂度 或可在 _079 time.4067920 中解出。
O(n)、O(n2) 等都是多项式时间。有些问题不能在多项式时间内解决。因此，世界上会使用某些东西。 Public Key Cryptography 就是一个很好的例子。在计算上很难找到一个非常大的数的两个质因数。如果不是，我们就不能使用我们使用的公钥系统。
无论如何，这就是我(希望是简单的英语)对 BigOh(修订版)的解释。