表示时间的大o符号，是用来描述算法效率的语言和度量单位。不彻底理解这个概念，不仅会影响你做出清晰的判断，还会让你无法评价算法的优劣。
例如某个o(2n)的算法实际上是o(n)。特定输入中，o(n)很有可能会比o(1)代码还要快。大o仅仅描述了增长的趋势。
应该舍弃无关紧要的项。比如 o(n2+n)变成o(n2)、o(n+logn)变成o(n)、o(5*2^n+1000n^100)变成o(2^n)等。
元素的个数每次减半，它的运行时间很可能是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)个节点存在。
如对本文有疑问， 点击进行留言回复！！
网友评论