33

什么是大 O 符号？你用它吗？

我想我错过了这门大学课：D

有没有人使用它并给出一些他们在哪里使用它的真实例子？

也可以看看：

八岁的Big-O？
Big O，您如何计算/近似它？
你在现实生活中应用了计算复杂性理论吗？

4

12 回答 12

41

大多数人在谈论 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 个项目需要多少时间，以及B相同的 100 个项目需要多少时间，并且A比的下降速度比其中一个慢得多BBABAA，它迟早会超越——这是肯定的）。

于 2008-09-25T12:57:10.350 回答
9

大 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 是不可变的。因此，每次在字符串上添加字母时，都必须创建一个新字符串。为此，您必须将旧字符串中的值复制到新字符串中并添加新字符。

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

这是(n^2-n)/2并且对于大 O 表示法，我们（通常）仅使用最高幅度因子并丢弃任何乘以它的常数，我们最终得到O(n^2).

使用类似 a 的StringBuilder方法将遵循 O(nLog(n))。如果您计算开头的字符数并设置容量，StringBuilder您可以得到它O(n)。

因此，如果我们有 1000 个字符的输入，第一个示例将执行大约 100 万次操作，StringBuilder将执行 10,000 次，而StringBuilderwithsetCapacity将执行 1000 次操作来做同样的事情。这是粗略估计，但O(n)符号是数量级，而不是精确的运行时间。

这不是我经常使用的东西。然而，当我试图找出做某事的最佳算法时，它一直在我的脑海里。

于 2008-09-25T12:51:05.167 回答
4

Big-O已经为 8 岁儿童提出了一个非常相似的问题？. 希望那里的答案能回答您的问题，尽管那里的提问者确实对这一切有一些数学知识，如果您需要更全面的解释，您可能没有那么清楚。

于 2008-09-25T12:32:46.647 回答
3

每个程序员都应该知道什么是大 O 表示法，它如何应用于具有常见数据结构和算法的动作（从而为他们正在解决的问题选择正确的 DS 和算法），以及如何为他们自己的算法计算它。

1）它是在处理数据结构时衡量算法效率的顺序。

2) 像 'add' / 'sort' / 'remove' 这样的动作对于不同的数据结构（和算法）可能会花费不同的时间，例如对于 hashmap，'add' 和 'find' 是 O(1)，但是 O (log n) 表示二叉树。在处理普通数组时，QuickSort 的排序是 O(nlog n)，而 BubbleSort 的排序是 O(n^2)。

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

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

于 2008-09-25T12:33:16.553 回答
3

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

事实证明，这在计算机科学中是一个非常有用的想法，尤其是在算法分析中，因为我们经常精确地关注函数的增长率，例如，表示两种不同算法所花费的时间。非常粗略地说，如果 t1 = O(t2) 对于足够大的 n（通常是问题-例如数组的长度或图中的节点数或其他。

这个规定，即 n 变得足够大，使我们能够提取很多有用的技巧。也许最常用的一个是您可以将函数简化为增长最快的项。例如 n^2 + n = O(n^2) 因为随着 n 变得足够大，n^2 项变得比 n大得多，以至于 n 项实际上是微不足道的。所以我们可以不考虑它。

然而，这确实意味着大 O 表示法对小 n 的用处不大，因为我们已经忘记的增长较慢的项仍然足以影响运行时。

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

哦，我用它吗？是的，一直以来——当我弄清楚我的代码有多高效时，它给出了一个很好的“粗略估计”的成本近似值。

于 2008-09-26T16:35:03.160 回答
3

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 notation的定义，它还指出 f(x) 对于某个常数 C 只需大于 C*g(x) （这只是另一种说法，你不能通过将 g(x) 乘以一个常数因子来帮助 g(x) 赢得比赛 - f(x) 最终总是会获胜）。正式定义也使用绝对值。但我希望我设法让它变得直观。

于 2009-06-03T04:34:44.967 回答
2

值得考虑的是，许多算法的复杂性都基于多个变量，尤其是在多维问题中。例如，我最近不得不为以下内容编写一个算法。给定一组 n 个点和 m 个多边形，提取位于任何多边形中的所有点。复杂性基于两个已知变量 n 和 m，以及每个多边形中有多少点的未知数。这里的大 O 表示法比 O(f(n)) 甚至 O(f(n) + g(m)) 更复杂。当您处理大量同质项目时，Big O 是很好的选择，但不要期望总是如此。

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

最后要考虑的是，算法的速度和它使用的空间量之间通常存在直接的权衡。 鸽子洞分类就是一个很好的例子。回到我的点和多边形，假设我所有的多边形都可以简单快速地绘制，我可以在屏幕上填充它们，比如用蓝色，每个固定的时间。因此，如果我在黑屏上绘制我的 m 个多边形，则需要 O(m) 时间。要检查我的任何 n 个点是否在多边形中，我只需检查该点的像素是绿色还是黑色。所以检查是O(n)，总分析是O(m + n)。当然，缺点是，如果我要处理毫米级精度的真实世界坐标，我需要近乎无限的存储空间......呵呵。

于 2008-09-27T16:06:30.960 回答
2

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

一个很好的例子是动态表，它基本上是一个随着您向其中添加元素而扩展的数组。一个简单的实现会为每个添加的元素将数组的大小增加 1，这意味着每次添加新元素时都需要复制所有元素。如果您使用此方法连接一系列数组，这将导致O(n 2 )算法。另一种方法是在每次需要更多存储空间时将阵列容量翻倍。尽管有时追加是一个O(n)操作，但您只需要为每添加n 个元素复制O(n)个元素，因此该操作平均为O(1)。这就是StringBuilder或std::vector已实现。

于 2008-09-27T16:19:44.627 回答
2

什么是大 O 符号？

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

我是否使用大 O 表示法？

我有时会使用 Big O 表示法向其他程序员传达算法的复杂性。当我考虑使用什么算法时，我一直在使用基础理论（例如大 O 分析技术）。

具体例子？

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

于 2009-10-18T14:27:14.667 回答
1

来自维基百科......

在分析算法以提高效率时，大 O 表示法很有用。例如，完成一个大小为 n 的问题所需的时间（或步骤数）可能被发现为 T(n) = 4n² - 2n + 2。

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

明明没用过。。

于 2008-09-25T12:34:46.580 回答
1

您应该能够评估算法的复杂性。这与它需要多少元素的知识相结合，可以帮助您确定它是否不适合其任务。

于 2008-09-25T12:39:58.423 回答
0

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

要搜索列表中的项目，您可以遍历列表直到找到该项目。在最坏的情况下，该项目位于最后。

假设列表中有 n 个项目。在最坏的情况下，您需要进行 n 次迭代。在大 O 概念中，它是 O(n)。

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

于 2008-09-25T12:34:45.830 回答