什么是大O表示法？你用它吗？[复制]

StackOverflow https://stackoverflow.com/questions/133008

题

这个问题在这里已经有答案了：

什么是大O表示法？你用它吗？

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

有人使用过它并给出一些现实生活中使用它的例子吗？

也可以看看：

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

有帮助吗？

解决方案

大多数人在谈论 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 比 B, ，您可以计算出物品的数量 B 将超越 A 速度（作为 B 下降速度比其中之一慢得多 A, ，它将超越 A 迟早——这是肯定的）。

其他提示

大 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;
}

现在想想这实际上是在做什么。它会遍历输入的每个字符并将它们加在一起。这看起来很简单。问题是 字符串是不可变的. 。因此，每次在字符串中添加一个字母时，都必须创建一个新字符串。为此，您必须将旧字符串中的值复制到新字符串中并添加新字符。

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

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

使用类似的东西 StringBuilder 将沿着 O(nLog(n)) 的路线。如果在开头计算字符数并设置容量 StringBuilder 你可以让它成为 O(n).

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

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

已经有人提出了一个非常类似的问题 八岁孩子的大O？. 。希望那里的答案能够回答您的问题，尽管那里的提问者确实有一些关于这一切的数学知识，如果您需要更全面的解释，您可能无法澄清这些知识。

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

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

2) 对于不同的数据结构（和算法），“添加”/“排序”/“删除”等操作可能会花费不同的时间，例如，对于哈希图，“添加”和“查找”是 O(1)，但对于(log n) 为二叉树。在处理普通数组时，快速排序的排序时间为 O(nlog n)，而冒泡排序的排序时间为 O(n^2)。

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

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

“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 来说不太有用，因为我们已经忘记的增长较慢的项仍然足以影响运行时间。

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

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

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) 带来了某种“速度限制”，因为最终它会超越它并永远将其抛在后面。

这并不完全是定义 大 O 表示法, ，其中还指出对于某个常数 C，f(x) 只需要大于 C*g(x)（这只是另一种说法，即您不能通过将 g(x) 乘以来帮助 g(x) 赢得竞争）常数因子 - f(x) 最终总是获胜）。正式定义也使用绝对值。但我希望我能够让它变得直观。

还值得考虑的是，许多算法的复杂性基于多个变量，特别是在多维问题中。例如，我最近必须编写以下算法。给定一组 n 个点和 m 个多边形，提取位于任意多边形中的所有点。复杂性基于两个已知变量 n 和 m，以及每个多边形中有多少个点的未知数。这里的大 O 表示法比 O(f(n)) 甚至 O(f(n) + g(m)) 复杂得多。当您处理大量同质项目时，大 O 很有用，但不要指望情况总是如此。

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

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

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

动态表就是一个很好的例子，它基本上是一个数组，当您向其中添加元素时，它会扩展。一种简单的实现方式是，每添加一个元素，数组的大小就会增加 1，这意味着每次添加新元素时都需要复制所有元素。这将导致 在2) 算法（如果您使用此方法连接一系列数组）。另一种方法是每次需要更多存储时将阵列容量加倍。尽管追加是一个 在） 有时操作只需复制即可 在） 每个元素 n 添加了元素，所以操作是 复杂度(1) 一般。事情就是这样 字符串生成器 或者 std::向量 已实施。

什么是大O表示法？

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

我使用 Big O 表示法吗？

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

具体例子？

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

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

大 O 表示法在分析算法效率时非常有用。例如，完成大小为 n 的问题所需的时间（或步数）可能为 T(n) = 4n² − 2n + 2。

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

显然我没用过。。

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

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

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

假设列表中有 n 个项目。在最坏的情况下，你会进行 n 次迭代。在大 O 表示法中，它是 O(n)。

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top