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

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

我猜错了这个大学课:D

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

也可以看看:

8岁儿童的大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迟早会超车- 这是肯定的).

Big 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个字符的输入,第一个例子将执行大约一百万个操作,StringBuilder将执行10,000个,并且StringBuilderwith setCapacity将执行1000个操作来执行相同的操作.这是粗略估计,但O(n)符号是关于数量级,而不是精确的运行时间.

这不是我定期使用的东西.然而,当我试图找出做某事的最佳算法时,它始终处于我的脑海中.