大O

表示时间的大o符号，是用来描述算法效率的语言和度量单位。不彻底理解这个概念，不仅会影响你做出清晰的判断，还会让你无法评价算法的优劣。

• 常量不算在运算时间里。

例如某个o(2n)的算法实际上是o(n)。特定输入中，o(n)很有可能会比o(1)代码还要快。大o仅仅描述了增长的趋势。

• 丢弃不重要的项

应该舍弃无关紧要的项。比如 o(n²+n)变成o(n²)、o(n+logn)变成o(n)、o(5*2^n+1000n^100)变成o(2^n)等。

•  logn运行时间

元素的个数每次减半，它的运行时间很可能是o(logn)。

以二分查找为例。假设一个排序数组长度为n，目标值为x。首先比较x与中值，如果x等于中值直接返回，如果小于中值，搜索数组的左边，如果大于中值，搜索数组的右边。

开始时有n个元素的排序数组要搜索，经过一次搜索之后，还剩下n/2个元素，再一次，剩下n/4个元素，直到找到目标值或者待搜索元素个数为1时才停止搜索。

同理，在平衡二叉搜索树中查找一个元素也是o(logn)，每次比较，非左即右。

• 递归的运行时间

当一个多次调用自己的递归函数出现时，它的运行时间往往是o(分支数^数的深度)，分支数即每次调用自己的次数。

例如：

int f(int n) {
  if (n <= 1) {
    return 1;
  }
  return f(n-1) + f(n-1);
}

运行时间是o(2^n)。

这个例子的空间复杂度为o(n)，尽管树节点总数为o(2^n)，但同一时刻只有o(n)个节点存在。