什么是Big O符号？你会用吗？

我想念这门大学班：D

是否有人使用它并提供一些现实生活中使用它的示例？

也可以看看：

大八岁的孩子？
大O，我们如何计算/近似？
我们是否在现实生活中应用了计算复杂性理论？

解决方案

Big-O已经针对八岁儿童提出了一个非常类似的问题？希望那里的答案能回答问题，尽管那里的提问者确实对此有一点数学知识，如果我们需要更全面的解释，可能就不必这么澄清了。

每个程序员都应该知道Big O表示法是什么，它如何应用于具有通用数据结构和算法的动作(从而为他们要解决的问题选择正确的DS和算法)，以及如何针对自己的算法进行计算。

1)这是衡量数据结构时算法效率的一个顺序。

2)诸如'add'/'sort'/'remove'之类的操作可能会花费不同的时间，并且具有不同的数据结构(和算法)，例如，对于哈希映射，'add'和'find'为O(1)，但是O (log n)表示二叉树。当处理纯数组时，对于QuickSort，排序为O(nlog n)，对于BubbleSort，排序为O(n ^ 2)。

3)通常可以通过查看算法的循环深度来进行计算。 O(n)没有循环，O(1)循环遍历所有集合(即使它们在某个点发生中断)。如果循环在每次迭代中将搜索空间减半？ O(log n)。将最高的O()用于一系列循环，并在嵌套循环时乘以O()。

是的，它比这更复杂。如果我们真的有兴趣，请教一本教科书。

它表示算法在最坏的情况下有多少次迭代。

要搜索列表中的项目，我们可以遍历列表，直到获得该项目。在最坏的情况下，该项目位于最后一位。

可以说列表中有n个项目。在最坏的情况下，我们需要进行n次迭代。在大O表示法中，它是O(n)。

它实际上说明了算法的效率。

来自维基百科.....

大O表示法在分析算法效率时很有用。例如，完成大小为n的问题所需的时间(或者步骤数)可能为T(n)= 4n2？ 2n + 2.

随着n的增大，n2项将占主导地位，因此可以忽略所有其他项，例如，当n = 500时，项4n2是2n项的1000倍。在大多数情况下，忽略后者对表达式的值的影响可以忽略不计。

显然我从未使用过它。

我们应该能够评估算法的复杂性。结合了解将使用多少元素的知识，可以确定它是否不适合其任务。

大O表示法表示算法的限制因素。它是算法运行时间如何相对于输入进行缩放的简化表示。

例如(在Java中)：

/** Takes an array of strings and concatenates them
  * This is a silly way of doing things but it gets the 
  * point across hopefully
  * @param strings the array of strings to concatenate
  * @returns a string that is a result of the concatenation of all the strings
  *          in the array
  */
public static String badConcat(String[] Strings){
    String totalString = "";
    for(String s : strings) {
        for(int i = 0; i < s.length(); i++){
            totalString += s.charAt(i);
        }
    }
    return totalString;
}

现在考虑一下这实际上在做什么。它正在经历输入的每个字符并将它们加在一起。这似乎很简单。问题在于String是不可变的。因此，每次将字母添加到字符串时，都必须创建一个新的String。为此，我们必须将值从旧字符串复制到新字符串中并添加新字符。

这意味着我们将复制第一个字母n次，其中n是输入中的字符数。我们将复制字符" n-1"次，因此总共将有"(n-1)(n / 2)"个副本。

这是(n ^ 2-n)/ 2，对于Big O表示法，我们通常仅使用最高的幅度因子，并减去与其相乘的任何常数，最后得到O(n ^ 2)。

使用类似StringBuilder这样的东西将遵循O(nLog(n))的思路。如果我们在开头计算字符数并设置StringBuilder的容量，则可以将其设置为O(n)。

因此，如果我们有1000个字符的输入，第一个示例将执行大约一百万个操作，StringBuilder将执行10,000个操作，而带有setCapacity的StringBuilder`将执行1000个操作来完成相同的操作。这是一个粗略的估计，但是" O(n)"表示法是大约数量级，而不是确切的运行时间。

这不是我经常说的话。然而，当试图找出最好的算法来做某件事时，它一直在我的脑海中回荡。

大多数人在谈论Big-O时忘记了一件重要的事情，因此我觉得有必要提一下：

我们不能使用Big-O比较两种算法的速度。 Big-O仅表示如果将处理的项目数量加倍，算法将变慢多少(大约)，或者如果将数量减少一半，则算法变快多少。

但是，如果我们有两种完全不同的算法，并且一个(A)是O(n ^ 2)，而另一个(B)是O(log n)，则不能说A比B慢。实际上，对于100个项目，" A"可能比" B"快十倍。它只是说，对于200个项目，A的增长速度将因n ^ 2而变慢，而B的增长速度将因其log n`而变慢。因此，如果我们同时对两者进行基准测试，并且知道" A"处理100个项目需要花费多少时间，并且对同一100个项目需要" B"处理多少时间，而" A"要比" B"更快，则可以计算出多少项目B的速度将超过A的速度(因为B的速度下降的速度比A的速度慢得多，这肯定早晚会超过A的速度)。

当n变得非常大时，使用" Big-O"表示法比较变量(例如n)的两个函数的增长率。如果函数f的增长比函数g的增长快得多，我们说g = O(f)表示对于足够大的n，f将始终大于g直到比例因子。

事实证明，这在计算机科学中，尤其是在算法分析中，是一个非常有用的想法，因为我们经常精确地关注函数的增长率，这些函数代表例如两种不同算法所花费的时间。粗略地讲，如果t1 = O(t2)对于足够大的n(通常为的"大小")，我们可以确定运行时间为t1(n)的算法比运行时间为t2(n)的算法更有效。像数组的长度或者图中的节点数之类的问题。

n足够大的这一规定允许我们提取许多有用的技巧。也许最常用的一种是我们可以简化功能，直到它们增长最快。例如n ^ 2 + n = O(n ^ 2)，因为随着n变得足够大，n ^ 2项变得比n大得多，以至于n项实际上无足轻重。因此，我们可以将其从考虑中删除。

但是，这确实意味着big-O表示法对小n的用处不大，因为我们忘记的较慢的增长术语仍然足够重要，足以影响运行时。

我们现在拥有的是一种工具，用于比较两种不同算法的成本，还有一种简略的说法，一种算法比另一种算法更快或者更慢。大O表示法可能会被滥用，因为它已经不够精确了，这是一个耻辱！有相等的用语可以说一个功能的增长速度不及另一个，并且两个功能以相同的速度增长。

哦，我用吗？是的，一直以来，当我弄清楚我的代码有多有效时，它都能为成本提供一个很好的近似值。

还可能值得考虑的是，许多算法的复杂性基于一个以上的变量，尤其是在多维问题中。例如，我最近不得不为以下内容编写算法。给定一组n个点和m个多边形，请提取位于任意多边形中的所有点。复杂度基于两个已知变量n和m，以及每个多边形中有多少个点的未知数。这里的大O符号比O(f(n))甚至O(f(n)+ g(m))涉及得多。
当我们处理大量同质物品时，Big O很好，但是不要总是这样。

还值得注意的是，数据上实际的迭代次数通常取决于数据。 Quicksort通常很快，但是给它预排序的数据会降低速度。基于对数据可能如何组织以及n和m的相对大小的先验知识，我的点和多边形alogorithm很快结束，接近O(n +(m log(m))。严重影响了相对大小不同的随机组织数据。

最后要考虑的是，算法的速度与其使用的空间量之间通常存在直接的权衡。鸽孔分拣就是一个很好的例子。回到我的点和多边形，可以说我所有的多边形都很容易绘制，并且可以将它们填充到屏幕上，例如以蓝色填充，每次固定的时间。因此，如果我在黑屏上绘制m个多边形，则需要O(m)的时间。要检查我的n个点中是否有一个位于多边形中，我只需检查该点处的像素是绿色还是黑色。因此检查为O(n)，总分析为O(m + n)。当然，缺点是，如果我要处理毫米级精度的真实世界坐标，我需要接近无限的存储空间。

还可能值得考虑摊销时间，而不仅仅是最坏的情况。例如，这意味着，如果我们运行该算法n次，则平均将为O(1)，但有时可能会更糟。

一个很好的例子是动态表，它基本上是一个数组，在我们向其中添加元素时会扩展。幼稚的实现会使添加的每个元素的数组大小增加1，这意味着每次添加新元素时都需要复制所有元素。如果使用此方法连接一系列数组，则将导致O(n2)算法。另一种选择是，每当我们需要更多存储时，将阵列的容量增加一倍。即使有时追加是O(n)运算，我们也只需要为每添加的n个元素复制O(n)个元素，因此该运算平均为O(1)。这就是StringBuilder或者std :: vector之类的实现方式。

Big-O背后的"直觉"

想象一下x上两个函数之间的"竞争"，因为x接近无穷大：f(x)和g(x)。

现在，如果从某个点开始(某个x)，一个函数总是比另一个函数具有更高的值，那么我们将此函数称为比另一个函数"更快"。

因此，例如，如果对于每一个x> 100，我们都看到f(x)> g(x)，则f(x)比g(x)"更快"。

在这种情况下，我们说g(x)= O(f(x))。 f(x)构成了g(x)的某种"限速"，因为最终它通过了它并永远留下来。

这不完全是big-O表示法的定义，它还指出，对于某个常数C，f(x)仅必须大于C * g(x)(这是另一种说法，我们不能通过乘以常数f(x)来帮助g(x)赢得比赛，最终总会获胜)。形式定义也使用绝对值。但是我希望我能使它直观。

什么是Big O符号？

大O表示法是一种表达算法需要与输入数据大小相关的许多步骤之间的关系的方法。这称为算法复杂度。例如，使用冒泡排序对大小为N的列表进行排序需要O(N ^ 2)个步骤。

我是否使用Big O表示法？

我有时会使用Big O表示法来将算法复杂性传达给其他程序员。当我考虑使用哪种算法时，我一直都在使用基础理论(例如Big O分析技术)。

具体的例子？

我已经使用复杂度分析的理论来创建高效的堆栈数据结构的算法，该结构不需要重新分配内存，并且支持平均O(N)的索引时间。我已经使用Big O表示法向其他人解释了该算法。我还使用复杂度分析来了解何时可以进行线性时间排序O(N)。