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

这是一个非常简化的解释，但我希望它涵盖了最重要的细节。

假设您的算法处理的问题取决于一些“因素”，例如我们将其命名为N和X。

根据N和X的不同，您的算法将需要进行一些操作，例如在最坏情况下，它需要执行3(N^2) + log(X)次操作。

由于大O符号不太关心常数因子（即3），因此您的算法的大O符号为O(N^2 + log(X))。它基本上意味着“您的算法在最坏情况下所需的操作数量随着这个值的变化而变化”。

大O表示任何函数的上限。我们通常用它来表达算法运行时间函数的上限。

例如：f(n) = 2(n^2) +3n 是代表假设算法运行时间的函数，大O表示法基本上给出了这个函数的上限，即O(n^2)。

这种表示法基本上告诉我们，对于任何输入的“n”，运行时间都不会超过大O表示法所表示的值。

另外，我同意以上详细回答的所有内容。希望这能有所帮助！

它代表算法在“长时间内”的速度。
打个比方，你不关心一个运动员能以多快的速度完成一百米短跑，甚至是五千米长跑。你更关心马拉松选手，最好是极限马拉松选手（这种比喻到此就失效了，你必须回归“长时间内”这个比喻意义上来）。
你可以安心离开了。
我之所以写这篇回答，是因为我惊讶于其他答案的数学和技术性质。第一句话中的“长时间”概念与计算任务中任意耗时相关。与人类容量有限不同，某些算法完成计算任务可能需要超过几百万年的时间。
那么诸如所有这些数学中的“对数”和“多项式”呢？事实证明，算法与这些数学术语是内在相关的。如果你要测量街区里所有孩子的身高，那么要花费与孩子数量相等的时间。这与“n^1”或只是“n”的概念密切相关，其中“n”仅仅表示街区里孩子的数量。在极限马拉松情况下，你正在测量你城市的所有孩子的身高，但你必须忽略旅行时间，并假设他们在一条线上都可以让你测量身高。（否则我们会跳过当前的解释。）
然后，假设你正在尝试按最短到最长的顺序排列孩子身高的列表。如果只是你社区的孩子，你可能只是用肉眼大致看一下得出有序列表。这就是“短跑”比喻，而在计算机科学中，我们真的不关心短跑，因为在能用肉眼看出东西时，为什么要使用计算机？
但是，如果你要排列整个城市所有孩子的身高列表，或者更好地说，你国家所有孩子的身高列表，那么你会发现如何排列与数学中的“log”和“n^2”密切相关。查找最矮孩子并将其名字写在一个单独的笔记本上，并从原始笔记本中划掉它是与数学上的“n^2”相关的（如果你考虑排列笔记本的前半部分，然后是后半部分，再合并结果，你会得到与“对数”内在相关的方法）。
最后，假设你必须先去商店买一把卷尺。这是一个在短跑中很重要的努力，例如测量街区的孩子，但当你正在测量城市中所有孩子时，你可以安全地忽略这个成本。这是与数学中删除低阶多项式项的内在联系。
我希望我已经解释清楚了大O符号仅仅是关于长期运行的，数学本质上与计算方式相连，而且去掉数学术语和其他简化方式与长期运行的联系非常普遍。
一旦你意识到这一点，你就会发现大O符号真的很容易，因为所有困难的高中数学都很容易消失。唯一困难的部分是分析算法以确定数学术语，但通过一些练习，你可以在分析过程中开始省略术语，并安全地忽略算法的大块内容，只关注与大O有关的部分。也就是说，你应该能够对大多数情况进行直观判断。
祝你大O愉快，这是我在计算机科学中最喜欢的事情——发现某些东西比我想象的要容易得多，然后在Google面试时向不熟悉的人炫耀，哈哈。

大O表示一类函数。

它描述了函数在大输入值时增长的速度。

对于给定的函数f，O(f)描述了所有函数g(n)，其中你可以找到一个n0和一个常数c，使得所有满足n>=n0的g(n)的值都小于或等于c*f(n)。

简单来说，O(f)是一组函数。也就是从某个值n0开始，增长速度比f慢或者不快的所有函数。

如果f(n)=n，则

g(n)=3n在O(f)中。因为常数因素并不重要。

h(n)=n+1000也在O(f)中，因为对于小于1000的所有值可能更大，但是对于大O只有巨大的输入才重要。

然而i(n)=n^2不在O(f)中，因为二次函数的增长速度比线性函数快。

“Big O”符号的简明英语解释是什么？
我想强调，“Big O”符号的主要动机是当算法的输入规模变得太大时，方程式中描述算法度量的某些部分（即常数、系数、项）变得如此微不足道，以至于我们会忽略它们。在忽略一些部分后幸存下来的方程式部分被称为该算法的“Big O”符号。
因此，如果输入规模并不大，则“Big O”符号（上界）的概念将不重要。

int sumArray (int[] nums){
    int sum=0;   // here we've 1 operation
    for(int i=0; i < nums.length;i++){   // we've n times
        sum += nums[i]; // taking initialization and assignments, 3 ops
    }
    return sum;
}

在上述算法中，假设你按如下方式找到了T(n)（时间复杂度）：

T(n) = 3*n + 2

要找到它的“大O”符号，我们需要考虑非常大的输入规模：

n= 1,000,000   -> T(1,000,000) = 3,000,002
n=1,000,000,000  -> T(1,000,000,000) = 3,000,000,002
n=10,000,000,000  -> T(10,000,000,000) = 30,000,000,002

让我们为另一个函数提供类似的输入：F(n) = n。

n= 1,000,000   -> F(1,000,000) = 1,000,000 
n=1,000,000,000  -> F(1,000,000,000) = 1,000,000,000
n=10,000,000,000  -> F(10,000,000,000) = 10,000,000,000

正文翻译：正如您所看到的，随着输入规模变得太大，T(n)约等于或越来越接近F(n)，因此常数2和系数3变得不那么重要，现在“大O符号”的概念出现了。
注：本段文字可能涉及计算机科学中的算法分析。

O(T(n)) = F(n)
O(T(n)) = n

我们说 T(n) 的大 O 是 n，符号表示为 O(T(n)) = n，它是在 n 变得非常大时 T(n) 的上限。同样的步骤适用于其他算法。

在简单的英语中，大 O 就像是小于等于符号。当我们说对于两个函数 f 和 g，f = O(g) 时，它意味着 f <= g。

然而，这并不意味着对于任何 n，都有 f(n) <= g(n)。实际上，它意味着f 在增长方面小于或等于 g。这意味着在某一点之后，如果 c 是常数，则 f(n) <= c*g(n)。而在某一点之后指的是对于所有 n >= n0，其中 n0是另一个常数。

大O符号 - 经济角度。

我最喜欢用的英文词汇来描述这个概念是你在完成一个任务时所支付的价格随着任务规模的增长而增加。

可以把它看作是一种重复性成本，而不是一开始需要支付的固定成本。因为成本只会增长并且不断累加，所以固定成本在整体来看变得微不足道。我们想要衡量它们相对于提供给设置的原材料（问题大小）增长的速度和何时会相应地增加。

然而，如果初始设置成本很高，而您只生产少量产品，您将希望查看这些初始成本 - 这些也被称为常数。

由于这些常数在长期内并不重要，这种语言使我们能够讨论超出我们正在运行的基础设施类型的任务。因此，工厂可以位于任何地方，工人可以是任何人-都没有关系。但是随着输入和输出的增长，工厂的规模和工人数量将成为我们可以长期改变的事物。

因此，这就成为了一个如何运行某物需要花费多少的大局观近似值。由于时间和空间是经济数量（即它们是有限的），因此它们都可以使用这种语言来表示。

技术说明：一些时间复杂度的例子 - O(n)通常意味着如果问题的规模为“n”，我至少需要查看每个部分。O(log n)通常意味着我将问题的大小减半并重复检查，直到任务完成。O(n^2)表示我需要查看一对事物（例如n个人之间在派对上握手）。

已经有一些很好的回答了，但我想以不同的方式做出贡献。如果您想要将发生的所有事情可视化，可以假设编译器在约1秒内可以执行近10^8个操作。如果输入是以10^8给出的，则可能需要设计一种以线性方式运行的算法（例如未嵌套的for循环）。 以下是可以帮助您快速确定要找出的算法类型的表格 ;)

如果我要向一个6岁的孩子解释这个问题，我会画一些函数，例如f(x) = x和f(x) = x^2，并问孩子哪个函数将是页面顶部的上方函数。然后我们会继续画图，并看到x^2获胜了。实际上，“谁赢了”其实就是当x趋近于无穷大时增长更快的函数。因此，“函数x在x^2的Big O表示法中”意味着当x趋近于无穷大时，x的增长速度比x^2慢。 当x趋近于0时，同样的方法也可以用。如果我们为从0到1的x绘制这两个函数，x将成为上方函数，因此“函数x^2在x趋近于0时的Big O表示法中”。 当孩子长大后，我会补充说，实际上Big O可以是一个增长方式与给定函数相同的函数，甚至常数也被丢弃。因此，2x在x的Big O表示法中。

当我们有一个函数，比如f(n) = n+3，并且我们想知道当n趋近于无穷大时它的图像是什么样子的，我们只需要舍弃所有常数和低阶项，因为它们在n变大时不重要。这样就剩下了f(n) = n，那么为什么我们不能只使用它呢？为什么我们需要寻找一些比我们的f(n) = n+3函数更高和更低的函数，即大O和大Omega。
因为在n趋近于无穷大时简单地说这个函数只是f(n) = n是不正确的，所以为了正确描述，我们需要找出包含f(n) = n+3的区域。我们对图像所在位置并不是很感兴趣，因为较低阶的项和常数并没有显著改变图像的增长，因此换句话说，上下限所包围的区域是我们的f(n) = n+3函数的模糊版本。
仅仅简单舍弃常量和低阶项就是找到上下界函数的过程。
根据定义，如果你可以找到一个常数，使得你可以将f(n) = n函数乘以这个常数，使得对于每个n输出结果都比原来的函数大（或者更小用于下界），那么该函数就是另一个函数的下限或上限。

f(n) = n*C > f(n) = n+3

是的，C = 2 可以做到这一点，因此我们的函数 f(n) = n 可以成为我们的函数 f(x) = x+3 的上界。

对于下界也是如此：

f(n) = n*C < f(n) = n+3

C = -2 将会实现它。

所以，f(x) = n 是 f(x) = x+3 的上限和下限，当它既是大O又是Omega时，它就是Theta，这意味着它是严格绑定的。

因此，大O也可以是 f(x) = x^2，因为它满足条件 f(n) = n^2*C > f(n) = n+3。它在我们的 f(n) = n+3 图形之上，但是这个上限和下限之间的区域不像我们之前的界限那样精确。