"Big O"符号的通俗易懂解释是什么？（这是一个关于IT技术的问题）

测量软件程序速度非常困难，而且当我们尝试时，答案可能会非常复杂，并充满例外和特殊情况。这是一个大问题，因为所有这些例外和特殊情况都会分散注意力，当我们想要比较两个不同的程序并找出哪一个“最快”时，这些内容是没有帮助的。

由于所有这些无用的复杂性，人们尝试使用最小和最简单的（数学）表达式来描述软件程序的速度。这些表达式是非常粗略的近似：虽然有点运气的话，它们将捕捉到一段软件是否快速的“本质”。

由于它们是近似值，我们在表达式中使用字母“O”（大Oh），作为一种惯例向读者发出信号，表明我们正在进行粗略的过度简化。（并确保没有人错误地认为表达式在任何方面都是准确的）。

如果你把“Oh”解读为“与...同级别”或“近似”，那么你不会走太远。 （我认为选择大Oh可能是一种幽默尝试）。

这些“大Oh”表达式唯一尝试做的就是描述软件在我们增加软件需要处理的数据量时减慢了多少。如果我们将需要处理的数据量翻倍，软件需要花费两倍的时间来完成工作吗？ 十倍的时间？实际上，您会遇到非常有限数量的大Oh表达式，需要关注：

好的：

• O(1) 常数: 程序无论输入的大小如何，运行时间都相同。
• O(log n) 对数: 即使输入的规模增加很大，程序的运行时间也只会缓慢增加。

不好的：

• O(n) 线性: 程序的运行时间与输入的大小成正比增加。

O(n^k) 多项式：处理时间随着输入规模的增加而逐渐增长，且呈现多项式函数的形式。

... 而且很糟糕：

• O(k^n) 指数：即使问题规模中等，程序运行时间也会非常快地增加，只有在处理小数据集时使用指数算法才是可行的。
• O(n!) 阶乘：程序的运行时间将比您能够承受的任何东西都要长，只有在处理非常小和看似微不足道的数据集时使用阶乘算法才是可行的。

以下是对Big O的简明英文解释：
在编程中，我们试图解决问题。我们编写的代码被称为算法。 Big O符号允许我们以标准化的方式比较算法的最坏情况性能。硬件规格随时间变化，硬件的改进可以缩短算法运行的时间。但是替换硬件并不意味着我们的算法有任何改进或提高，因为我们的算法仍然是相同的。因此，为了使我们能够比较不同的算法，确定哪一个更好，我们使用Big O符号。
不是所有算法都需要相同的时间来运行，并且可能会根据输入中的项目数量而变化，我们将其称为n。基于此，我们考虑最坏情况分析，或者随着n越来越大的运行时间的上限。我们必须知道n是什么，因为许多Big O符号引用它。

好的，我来谈谈我的看法。

大O表示程序消耗的资源随问题实例大小的增加速率。

资源可以是CPU时间总量，也可以是最大RAM空间。默认情况下，指的是CPU时间。

比如说问题是“求和”，

int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}

问题实例= {5,10,15} ==> 问题实例大小 = 3，循环中的迭代次数= 3

问题实例= {5,10,15,20,25} ==> 问题实例大小 = 5，循环中的迭代次数= 5

对于输入大小为“n”的程序，它在数组中以“n”次迭代速度增长。因此，大O表示为O（n）。

假设问题是“查找组合”，

    void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }

问题实例= {5,10,15} ==> 问题实例大小= 3，总迭代次数= 3*3 = 9

问题实例= {5,10,15,20,25} ==> 问题实例大小= 5，总迭代次数= 5*5 =25

对于输入规模为“n”的程序，在数组中的迭代速度是“n*n”。因此，其时间复杂度为 O(n²)。

一个简单明了的答案可以是：

大O表示算法的最坏时间/空间情况。该算法永远不会占用超过该限制的空间/时间。大O表示在极端情况下的时间/空间复杂度。

大O符号是一种用于描述算法在空间或运行时间上限的方法。n代表问题中元素的数量（例如数组大小、树中节点数等）。我们关心的是随着n变大，描述运行时间。

当我们说某个算法的复杂度为O(f(n))时，我们指的是该算法的运行时间（或所需空间）始终低于某个常数乘以f(n)。

说二分查找的运行时间为O(logn)意味着存在一个常数c，可以将log(n)乘以该常数，得到的结果始终大于二分查找的运行时间。换句话说，您将始终具有某个对数(n)比较的恒定因子。

换言之，如果g(n)是您的算法的运行时间，那么当n > k 且 g(n) <= c*f(n)时，我们说 g(n) = O(f(n)),其中c和k是某些常数。

"请用尽可能简单的数学方式，对Big O进行通俗易懂的解释。"
这样一个简单明了的问题值得得到同样简洁的回答，就像教学辅导中的回答一样。
“Big O表示算法运行在输入数据量下所需的时间”，这是Big O符号的简单定义。
（*以一种美妙的、无单位的时间来衡量！）
（**这很重要，因为无论人们是今天还是明天，他们总是想要更多）

• 实际上，大 O 分析非常有用且重要，因为它将焦点直接放在算法的复杂度上，并完全忽略了任何仅仅是比例常数的东西 - 比如 JavaScript 引擎、CPU 速度、您的互联网连接以及所有那些很快就会变得像 T 型车一样过时的东西。大 O 只关注性能问题，对现在和未来的人们都同等重要。

• 大 O 表示法还直接突出了计算机编程/工程的最重要原则，这个事实激励着所有优秀的程序员不断思考和梦想：超越技术的缓慢前进，唯一的方法是发明更好的算法。

算法示例（Java）：

public boolean search(/* for */Integer K,/* in */List</* of */Integer> L)
{
    for(/* each */Integer i:/* in */L)
    {
        if(i == K)
        {
            return true;
        }
    }
    
    return false;
}

算法描述：

• 该算法逐项搜索列表，查找关键字。

• 在列表中迭代每个项目，如果它是关键字，则返回True。

• 如果循环结束而没有找到关键字，则返回False。

大O符号表示复杂度的上界（时间、空间等）

要查找时间复杂度的大O值：

• 计算最坏情况需要多少时间（关于输入大小）：

• 最坏情况：关键字不存在于列表中。

• 时间（最坏情况）= 4n + 1

• 时间：O(4n+1) = O(n) | 在大O符号中，常数被忽略

• O(n) ~ 线性

还有大Omega符号，代表最佳情况下的复杂度：

• 最佳情况：关键字是第一项。

• 时间（最佳情况）= 4

• 时间：Ω(4) = O(1) ~ 即时\常数

大O符号是一种描述算法在给定任意数量的输入参数（我们称之为“n”）时运行速度的方式。它在计算机科学中非常有用，因为不同的机器以不同的速度运行，仅仅说一个算法需要5秒并不能告诉你太多信息，因为虽然你可能正在运行一个4.5 GHz八核处理器的系统，但我可能正在运行一个15年前的800 MHz系统，无论算法如何，我的系统都可能需要更长时间。因此，我们不是按时间指定算法运行速度，而是按输入参数的数量或“n”来指定算法运行速度。通过这种方式描述算法，我们能够比较算法的速度，而不必考虑计算机本身的速度。

大O符号

当 x 趋近于 a（例如，a = +∞）时，f(x) = O(g(x)) 的意思是存在一个函数 k，满足：

1. f(x) = k(x)g(x)

2. k 在 a 的某个邻域内有界（如果 a = +∞，则这意味着存在数字 N 和 M，使得对于每个 x > N，|k(x)| < M）。

换句话说，在 a 的邻域内，f(x) = O(g(x)) 表示 f 可以分解为 g 和某个有界函数的乘积。

小o符号

顺便提一下，这里是小o的定义。

当 x 趋近于 a 时，f(x) = o(g(x)) 的意思是存在一个函数 k，满足：

1. f(x) = k(x)g(x)

2. 当 x 趋近于 a 时，k(x) 趋近于 0。

例子

• 当 x 趋近于 0 时，sin x = O(x)。

• 当 x 趋近于 +∞ 时，sin x = O(1)。

• 当 x 趋近于 0 时，x² + x = O(x)。

• 当 x 趋近于 +∞ 时，x² + x = O(x²)。

• 当 x 趋近于 +∞ 时，ln(x) = o(x) = O(x)。

注意！等号“=”的符号使用的是“假等式”：o(g(x)) = O(g(x))是成立的，但是O(g(x)) = o(g(x))是不正确的。同样地，“当x → +∞时，写ln(x) = o(x)”是没问题的，但是公式“o(x) = ln(x)”是毫无意义的。

更多例子：

• 当n → +∞时，O(1) = O(n) = O(n²)（但反过来并不成立，等式是“假的”）

• 当n → +∞时，O(n) + O(n²) = O(n²)

• 当n → +∞时，O(O(n²)) = O(n²)

• 当n → +∞时，O(n²)O(n³) = O(n⁵)

---

这是维基百科文章：https://en.wikipedia.org/wiki/Big_O_notation

你想了解关于大O的所有内容吗？我也是。

因此，为了谈论大O，我将使用只有一个音节的单词。每个单词只有一个声音。小单词很快。你知道这些单词，我也知道。我们将使用只有一个声音的单词。它们很小。我相信你会认识我们将使用的所有单词！

现在，让你和我谈谈工作。大多数时候，我不喜欢工作。你喜欢工作吗？也许你喜欢，但我肯定不喜欢。

我不喜欢去上班。我不喜欢花时间在工作上。如果可以的话，我只想玩，做有趣的事情。你和我感觉一样吗？

现在有时候，我确实需要去上班。这很可悲，但却是真的。所以，当我在工作时，我有一个规则：尽量少做工作。尽可能接近不做任何工作。然后我去玩！

所以这里有个大消息：大 O 可以帮助我不用做工作！如果我知道大 O，我可以玩更多的时间。少做工作，多玩！这就是大 O 帮助我的方式。
现在我有一些工作要做。我有这个列表：one，two，three，four，five，six。我必须添加此列表中的所有内容。
哇，我讨厌工作。但是嘛，我必须这样做。所以我开始了。
一加二等于三...再加上三等于六...四是...我不知道。我迷失了。这对我来说太难了。我不太喜欢这种工作。
所以我们不要做这项工作。你和我只需要考虑它有多难。我要做多少工作才能将六个数字相加？
好吧，让我们看看。我必须先加一和二，然后将其加到三，然后将其加到四...总而言之，我数了六个加法。我必须做六个加法才能解决这个问题。
大 O 来了，告诉我们这个数学有多难。
大O表示：我们必须进行六次加法才能解决这个问题。每一件事情从1到6都需要进行一次加法。六个小工作...每一个小工作都是一次加法。
好吧，我现在不会做加法。但我知道它有多难。这将需要六次加法。
哦不，现在我有更多的工作要做。天哪。谁制造这种东西？！
现在他们让我从1加到10！我为什么要这样做？我不想把1加到6。要从1加到10...那就更难了！
它会更难多少？我需要做更多或更少的步骤？
嗯，我想我必须做十次加法...每一件事情从1到10都需要进行一次加法。十比六更多。要从1加到10，我必须做更多的工作，比从1加到6还要多！
我现在不想做加法。我只想想一下要添加那么多的难度。而且，我希望尽快玩耍。
要从一加到六，那是些工作。但你看，要从一加到十，那就更多的工作了。
大O表示法是我们的朋友。它可以帮助我们思考我们需要做多少工作，这样我们就可以计划。如果我们和大O成为朋友，它还可以帮助我们选择不那么困难的工作！
现在我们必须做新的工作。哦，不。我根本不喜欢这个工作。
新的工作是：将所有东西从一加到n。
等等！n是什么？我错过了吗？如果你不告诉我n是什么，我怎么能从一加到n呢？
好吧，我不知道n是什么。我没有被告知。你呢？没有？哦，好吧。所以我们现在不能完成这项工作。太好了。
但是尽管我们现在不会做这项工作，如果我们知道n的话，我们可以猜测它有多难。我们需要加上n件事情，对吧？当然！
现在大O登场了，他会告诉我们这项工作有多难。他说：逐个将所有事物从1加到N是O(n)。为了将所有这些东西相加，[我知道我必须加n次。][1] 这就是大O！他告诉我们做某种类型的工作有多难。
对于我来说，我认为大O就像一个大而慢的老板。他思考工作，但不去做它。他可能会说：“那项工作很快。”或者他会说：“那项工作很慢且困难！”但他不会做这项工作。他只是看着工作，然后告诉我们可能需要多长时间。
我非常关心大O。为什么？我不喜欢工作！没有人喜欢工作。这就是为什么我们都喜欢大O！他告诉我们可以工作多快。他帮助我们思考工作有多难。
哦，更多的工作。现在，让我们不去做这项工作。但是，让我们制定一个一步一步完成它的计划。
他们给了我们一副由十张牌组成的牌组。它们都混在一起：七、四、二、六...一点也不整齐。现在...我们的工作是对它们进行排序。
唉，这听起来好像很费力！
我们如何对这副牌进行排序？我有一个计划。
我将逐对地查看每张卡片，从第一张到最后一张，一对一对地进行比较。如果一对中的第一张卡片很大，而下一张卡片很小，我就交换它们。否则，我就进入下一对卡片，以此类推……很快，整副牌就排好了。
当整副牌排好后，我会问自己：我在这个过程中交换了卡片吗？如果是，我必须再次从头开始进行排序。
在某个时候，总会出现没有任何交换的情况，我们对牌组的排序就完成了。这需要很多工作！
那么，按照这些规则对牌组进行排序需要多少工作呢？
我有十张牌。通常情况下——也就是说，如果我没有太多运气的话——我必须遍历整副牌高达十次，并且每次遍历整副牌最多要交换十张牌。

大O, 帮帮我！

大O走了进来说：对于一叠n张牌，按这种方式排序需要O(N平方)的时间。

他为什么会说n的平方呢？

你知道n的平方是n乘以n。现在我懂了：检查n张卡片，可能要通过这个牌堆n次。这是两个循环，每个循环有n个步骤。工作量非常大，它是n平方。确实是很多工作量！

现在当大O说需要O(n平方)的工作量时，他并不是指精确的n平方加法。它可能会小一点，对于某些情况而言。但是在最坏的情况下，将近需要进行n平方步的工作来排序这叠牌。

现在这里大O是我们的朋友。

大O指出了这一点：随着n变得越来越大，当我们对卡片进行排序时，工作量比旧的“只需添加这些内容”工作要多得多。我们怎么知道呢？

嗯，如果n变得真的很大，我们就不用关心我们可能添加到n或n平方的任何东西了。

对于大n，n平方比n更大。

大O告诉我们，排序比添加更难。对于大的n来说，O(n平方)比O(n)更难。这意味着：如果n变得非常大，那么对n个物品进行排序必须花费比只是添加n个混合物更多的时间。
大O不能为我们解决工作。它告诉我们工作有多难。
我有一副牌。我已经将它们排序了。你帮了忙。谢谢。
有更快的方法可以排序吗？大O能帮助我们吗？
是的，有更快的方法！学习需要一些时间，但它有效...而且速度相当快。您也可以尝试它，但每个步骤都要仔细，并且不要失去自己的位置。
在这种新的排序方式中，我们不再像以前那样检查一对卡牌。以下是排序这副牌的新规则：
第一步：我选择我们现在正在处理的牌组中的一张牌。如果您愿意，您可以为我选择一张。（第一次执行此操作时，“我们现在正在处理的牌组”当然是整副牌。）
第二步：我将牌堆展开到你选择的那张牌上。什么是展开；我怎样才能展开呢？好吧，我从起始牌开始，逐一往下查找，寻找比展开牌更高的牌。
第三步：我从末尾牌开始向上查找，寻找比展开牌更低的牌。
一旦我找到这两张牌，我就交换它们，并继续寻找要交换的牌。也就是说，我回到第二步，在你选择的牌上进行更多的展开。
在某个时候，这个循环（从第二步到第三步）将会结束。当这个搜索的两个部分在展开牌处相遇时，它就结束了。然后，我们刚刚用你在第一步选择的牌展开了整副牌。现在，靠近起始位置的所有牌都比展开牌低；而靠近末尾的所有牌都比展开牌高。酷毙了！

第四步（这是有趣的部分）：我现在有两个小牌组，一个比展开卡更低，一个比展开卡更高。现在我要在每个小牌组上按步骤一来做！也就是说，我从第一个小牌组的步骤一开始，当完成工作后，我再从下一个小牌组的步骤一开始。

我把牌组分成几个部分，并对每个部分进行排序，逐渐变得更小，直到有些时候我没有其他工作要做了。现在，这可能看起来很慢，因为有许多规则。但是相信我，它根本不慢。它比第一种排序方式要少得多！

这种排序叫什么？它被称为快速排序！这种排序是由C. A. R. Hoare发明的，他将其称为快速排序。现在，快速排序一直被广泛使用！

快速排序将大的牌组分解成小的牌组。也就是说，它将大任务分解成小任务。

嗯，我认为其中可能有一个规则。要使大任务变小，请将其分解。

这种排序非常快。有多快呢？大O告诉我们：平均情况下，此排序需要执行O（n log n）的工作量。
比第一种排序更快还是更慢？求大O帮忙！
第一种排序是O(n²)。但是快速排序是O(n log n)。你知道当n很大时，n log n小于n²吗？这就是我们知道快速排序快的原因！
如果你要对一副牌进行排序，最好的方法是什么？嗯，你可以自己决定，但我会选择快速排序。
为什么我会选择快速排序？当然是因为我不想努力工作！我想尽快完成工作。
我如何知道快速排序需要较少的工作量？我知道O(n log n)小于O(n²)。 O更小，因此快速排序要做的工作较少！
现在你认识我的朋友大O了。他帮助我们做更少的工作。如果你知道大O，你也可以做更少的工作！
你从我这里学到了所有这些！你真聪明！非常感谢你！
现在工作完成了，让我们去玩吧！

---

[1]: 有一种方法可以欺骗，一次性将从1到n的所有东西都加起来。某个名叫高斯的孩子在8岁时发现了这个方法。虽然我不聪明，所以不要问我他是如何做到的。