O(n)：用于算法复杂度的大O符号表示法

21CTO导读：大O符号，英语称为Big O Notation，用于描述算法复杂度的渐进表示，它描述了算法如何通过其增长的上界来执行扩展。

 
大O算法是我在大学教过的东西之一，但是我其实从来没有掌握过这些概念，读书时我自己觉得能够足够回答这个符号的基本问题。
 
从那时候起没有什么任何改变。从我参加工作以来，也没有用过，也很少听到其他的同事提起过它。
 
在本文中，我想花一些时间来写一篇文章来总结大写O算法的基础知识 ，包括一些代码实例来辅助说明。
 
Big O Natiation是什么？来简单解释一下：
 
1、它是算法复杂度的相对表示方式
2、它描述了算法如何执行与扩展
3、它描述了函数增长能力的上限，可以理解为最不好的情形
 
快速查看算法：O(n2).
 
其中：n是函数作为输入接收的元素个数。上面的公式表示有n个输入，其复杂度为(n2)，这是一种速度较慢的排序算法。
 

表1：共同复杂度的比较

 
从上表中可以看到，随着函数的算法复杂度不断增加，完成函数所需要的时间越明显增加。在编程过程中，我们希望让这种递增尽可能地低，如果某个函数在输入增加时不能很好的扩展，那么极有可能导致性能糟糕的问题。
 

程序员还是适合用代码说话，下面的代码用Java编写，将有助于你清晰了解算法复杂度是如何影响性能的。
 
O(1)
 
public boolean isFirstNumberEqualToOne(List numbers){
return number.get(0) == 1;
}
 
O(1)为提供一个函数，始终通过外部获得固定的输入参数。
 
O(n)
 
public boolean containsNumber(List numbers, int comparisonNumber) {
  for(Integer number : numbers) {
    if(number == comparisonNumber) {
      return true;
    }
  }
  return false;
}
 
O(n)表示函数的复杂性，也称线性时间，该函数线性增加并与输入数量成正比。 这是Big O Notation如何描述最糟糕情况的一个很好例子，因为函数可以在读取第一个元素后返回true，或者在读取所有n个元素后返回false。这样的算法包括简单查找。
 
O(n2)
 
public static boolean containsDuplicates(List input) {
  for (int outer = 0; outer < input.size(); outer++) {
    for (int inner = 0; inner < input.size(); inner++) {
      if (outer != inner && input.get(outer).equals(input.get(inner))) {
        return true;
      }
    }
  }
  return false;
}
 
O(n2)表示其复杂度与输入大小的平方成正比的函数。 通过输入添加更多嵌套迭代将增加复杂度，其可以表示为具有3次总迭代的O(n3) 和具有4次总迭代的O(n4) 。
 
O(2n)
 
public int fibonacci(int number) {
    if (number <= 1) {
       return number;
    } else {
      return fibonacci(number – 1) + fibonacci(number – 2);
    }
}
 
O(2[size=25]n) 表示一个函数，其性能对于输入中的每个元素都加倍。 这个例子是Fibonacci数组的递归计算。 该函数属于O(2n) ，因为函数递归式为每个输入数字调用两次，直到该数字小于或等于1。[/size]
 
O(log n)
 
public boolean containsNumber(List numbers, int comparisonNumber) {
   int low = 0;
   int high = numbers.size() – 1;
   while (low <= high) {
        int middle = low + (high – low) / 2;
        if (comparisonNumber < numbers.get(middle)) {
           high = middle – 1;
        } else if (comparisonNumber > numbers.get(middle)) {
           low = middle + 1;
        } else {
           return true;
        }
  }
  return false;
}
 
O(log n) ，也称对数时间，表示随着输入大小的增加其复杂度以对数方式增加的函数。 这使得O(log n) 函数可以很好地扩展，因此处理较大的输入不太可能导致性能问题。 上面的示例使用二进制搜索来检查输入列表是否包含特定数字。
 
简单来说，它在每次迭代时将列表拆分为两个，直到找到数字或读取最后一个元素。 该方法具有与O(n)[size=19] 示例相同的功能 – 尽管实现完全不同并且更难以理解。 但是，通过更大的输入可以获得更好的性能（如上表中所示）。[/size]
 
小结
 
当前，我们获得的启示如下：
 
1 算法的速度指的并非时间，非操作数的增速
2 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加
3 算法的运行时间用大O表示法表示
4 O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。
 
关于Big O Notation还能写出很多内容。希望大家对Big O Notation的含义以及如何将其转换为自己编写的代码有一个基本概念。

作者：老夏