什么是大O符号？ 你使用它？ [重复](What is Big O notation? Do

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

• 什么是“大O”符号的纯英文解释吗？ 39个回答

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

我错过了这所大学班我猜：d

是否有人使用它，并给他们使用它的一些现实生活中的例子？

---

也可以看看：

大澳的八岁儿童？
大O，你怎么计算/近似它？
你申请在现实生活中的计算复杂性理论？

Answer 1:

大多数人在谈论大O时不要忘记一个重要的事情，所以我觉得有必要提及的是：

不能使用大O来比较两种算法的速度 。 大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迟早-这是肯定的）。

Answer 2:

大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)

使用像一个StringBuilder将沿的O线（n日志（N））。 如果计算出的字符数在开始和设置的容量StringBuilder你可以得到它是O(n)

所以，如果我们有输入1000个字符，第一个例子将大约进行百万次操作， StringBuilder将执行10000和StringBuilder与setCapacity将执行1000个操作做同样的事情。 这是粗略的估计，但O(n)符号是关于大小，不准确运行的命令。

这不是我说每使用定期。 它试图找出做事情最好的算法然而，当是，不断在我脑海里的后面。

Answer 3:

一个非常类似的问题已经被要求在大澳的八奥尔兹年？ 。 希望答案会有回答你的问题，虽然这个问题提问者那里确实有一些关于这一切，你可能没有数学知识，如果你需要一个更全面的解释，从而澄清。

Answer 4:

每个程序员都应该知道什么大O符号，它是如何适用于使用常用数据结构和算法操作（因而挑选他们解决问题的正确的DS和算法），以及如何计算它自己的算法。

1）它是在一个数据结构中工作时的算法的效率的测量的顺序。

2）像“添加” /“排序” /“删除”操作可以采取不同的时间量与不同的数据结构（和算法），例如，“添加”和“发现”是O（1）对于一个HashMap，但ö （log n）的一个二叉树。 排序是O（n日志n）的用于快速排序，但为O（n ^ 2）冒泡，用一个普通的阵列的时候。

3）计算可以通过在你的算法的循环内深度一般都希望来完成。 没有循环，O（1），循环遍历所有集合O（n）的（即使他们在某个时刻爆发）。 如果环路上减半每次迭代的搜索空间？ O（log n）的。 举个循环的顺序最高的O（），并乘以O（）时，嵌套循环。

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

Answer 5:

“大O”符号是用来比较的变量的两个函数的增长率（比如说N）正变得非常大。 如果函数f比函数g更迅速的增长，我们说，G = O（F）暗示了足够大的N，F 永远是除G高达缩放系数较大。

事实证明，这是计算机科学，特别是在算法分析非常有用的想法，因为我们往往正是关注功能的增长率代表，例如，通过两种不同的算法所需要的时间。 很粗，我们可确定与运行时间t1（n）的一个算法是比如果运行时间t2（N）的算法更高效的T1 = O（T2）为足够大的n通常是在的“尺寸”问题 - 像图中的或任何节点的阵列或数目的长度。

这一规定，使得n变得足够大，可以让我们拉了很多有用的技巧。 也许最经常使用的一个是可以简化的功能到他们的增长速度最快的条款。 例如，n ^ 2 + N = O（N ^ 2），因为当n增加足够大，则N ^ 2术语变得比n表示n个术语实际上是无关紧要的要大得多 。 因此，我们可以考虑将其删除。

然而，这并不意味着大O符号是小的N用处不大，因为我们已经忘记了缓慢的生长条件仍不够显著影响运行时间。

我们现在已经是比较两种不同的算法成本的工具，并说一个比另一个更慢或更快的简写。 大O符号可以被滥用这是一种耻辱，因为它是不准确的已经够了！ 有这么说的功能少快于另一个增长，而且两个函数增长以同样的速度相当的条款。

哦，我使用它？ 是的，所有的时间 - 当我搞清楚我的代码是如何有效的它给人很大的“背的最envelope-一个近似的成本。

Answer 6:

该“Intuitition”落后大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符号 ，其还指出，F（X）只比C * G（x）的一些常数C大（这是说的只是另一种方式，你不能帮助G（X）由常数因子乘以它在竞争中胜出 - F（X）最终将永远是赢家）。 正式定义也使用绝对值。 但我希望我设法使它直观。

Answer 7:

该许多算法复杂性是基于一个以上的变量，特别是在多维问题也可能是值得考虑的。 比如，我最近写了下面的算法。 给定一组n个点，并且m多边形，提取所有位于任何多边形的点。 复杂性是基于两个已知变量，n和m，以及有多少点是每个多边形未知。 这里的大O符号比O（F（N））或甚至ö更多地参与相当多的（F（N）+ G（M））。 大O是好的，当你在处理大量同质项目，但不要指望这始终是这种情况。

还值得一提的是，在数据迭代的实际数量往往是依赖于数据。 快速排序通常非常快，但给它预先排序的数据，它会减慢。 我点和多边形算法FFT结束了相当快，接近O（N +（M日志（M））的基础上，如何将数据很可能是有组织的n和m的相对大小先验知识。这将倒下严重上随机组织不同的相对大小的数据。

要考虑的最后一件事是，往往是直接的权衡算法的速度和空间，它使用的量之间。 鸽子洞排序就是一个不错的例子。 让我们回到我的点和面，可以说我所有的多边形是简单和快速的画，我可以借鉴他们充满屏幕，说为蓝色，在每个固定时间量。 所以，如果我画一个黑色的屏幕上我的个多边形，将采取O（M）的时间。 要检查我的任何n个点是多边形的，我只是检查在该点的像素是绿色或黑色。 因此，检查是O（n），以及总的分析是O（M + N）。 当然缺点是，我需要接近无穷大的存储，如果我处理现实世界的坐标精确到毫米。......嗬嗡嗡声。

Answer 8:

这也可能是值得考虑的分期时间，而不仅仅是最坏的情况。 这意味着，例如，如果你运行的算法N次，这将是平均O（1），但有时可能会更糟。

一个很好的例子是一个动态表，它基本上是膨胀，添加元素时它的阵列。 幼稚的执行将通过1的每个元素增加阵列的尺寸增加，这意味着所有的元素需要每一个新加的时间来被复制。 这将导致一个O（n ^2）的算法，如果你在串联了一系列使用这种方法阵列。 另一种方法是每次你需要更多的存储时间阵列的容量增加一倍。 即使追加是一个O（n）的操作有时候，你只需要复制O（n）的元素添加每n个元素，所以操作（1）平均为O。 这之类的东西的StringBuilder或std :: vector的是如何实现的。

Answer 9:

什么是大O符号？

大O符号是表达一种算法将需要与输入的数据的大小的许多步骤之间的关系的方法。 这被称为算法复杂。 例如排序的使用冒泡排序大小为N的列表需要O（N ^ 2）的步骤。

我用大O符号？

我使用的场合大O符号传达算法的复杂性同胞的程序员。 我用的基本理论（如大O分析技术）所有的时间，当我思考什么算法使用。

具体的例子吗？

我已经使用复杂分析的理论来创建用于要求不存储器再分配，并支持用于索引的O（N）时间平均有效堆栈数据结构的算法。 我用大O符号来解释算法给其他人。 我还使用复杂分析，以了解当线性时间排序O（N）是可能的。

Answer 10:

维基百科.....

分析效率算法时大O符号是非常有用的。 例如，时间（或步数），以便完成大小为n的问题可能会被发现是T（N）=4n² - 2N + 2。

当n变大时，N²任期将于占据主导地位，使所有其他条件可以忽略不计 - 例如，当n = 500，术语4n²是1000倍大的2n个任期。 忽略后者会对表达式的值在大多数情况下可以忽略不计的影响。

很显然，我从来没有使用过..

Answer 11:

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

Answer 12:

它说，算法的迭代次数在最坏的情况下。

搜索项目在列表中，你可以直到你得到了项目遍历列表。 在最坏的情况下，该项目是在最后的地方。

比方说，有列表中的N项。 在最坏的情况下，你需要n次迭代。 在大O notiation它是O（n）。

它说的算法factualy是多么有效。

文章来源: What is Big O notation? Do you use it? [duplicate]