大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;
}
现在想想这实际上在做什么。 它正在经历输入的每个字符并将它们加在一起。 这似乎很简单。 问题在于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已经在八岁时问过一个类似的问题？ 希望那里的答案能回答你的问题，尽管问题提问者确实有一些关于它的数学知识，如果你需要更全面的解释，你可能没有这么明确。
链接地址: http://www.djcxy.com/p/6741.html