上一节我们使用了两种不同的方式来获得两个数的最大公约数，那么如何判断我们应该使用哪一种方式呢？这里就涉及到了算法的时间复杂度、空间复杂度、稳定性等几个方面的因素，这次我们要讨论的大O表示法就是用来表示时间复杂度。
大O表示法法让你能够比较操作数，它指出了算法运行时间的增速——《算法图解》
开始前的准备
在开始学习之前请先确认一下你是否还记得高中所学的对数。
$$ \log_{3}9 $$
如果你可以一眼看出这个对数的结果是3，那么我们就可以进入接下来的部分了。
什么是大O表示法
大O表示法是一种特殊的表示法，指出了算法的运算速度有多快。
首先我们来看一个函数，当我们输入n时，函数的结果是1+2+...+n的和。
int add(int n){
int a=0; //第1行
int i; //第2行
for(i=1;i<=n;i++){ //第3行
a+=i; //第4行
}
return a; //第5行
}在这里for语句需要执行n次，我们就称他是时间复杂度为O(n)。
之所把他叫做大O表示法，仅仅因为操作数前面有一个大O。
这里我们可以再看一个二分查找的例子，二分查找类似于我们小时候玩的猜数游戏，当你猜一个数时，你的小伙伴会告诉你这个数是否正确，偏大了还是偏小了。直到你最终猜出正确的答案。比如我们猜1-100中的一个数，我们会猜50，得到结果之后就可以把范围缩小到1-50或者51-100，以此类推。每次我们都能将查找的范围缩小一半。
所以我们每次的查找范围就是n,n/2,n/4,....直到
$$ n/2^k $$
其中k就是循环的次数,随着k的增大，他们的比值将越来越接近于1。
令
$$ n/2^k=1 $$
可得
$$ k=\log_2 N $$
即当我们需要在长度为N的表上查找的时候，最多需要查找的次数是
$$ \log_2 N $$
所以二分查找的时间复杂度即为
$$ O(\log_2 N) $$
注意事项：算法的速度并非指时间，而是操作数的增速。
常见的大o运行时间
1.
$$ O(\log_x N) $$
这样的算法包括二分查找
2.
$$ O(N) $$
这样的算法包括简单查找
3.
$$ O(N*\log_x N) $$
这样的算法包括快速排序
4.
$$ O(N)^2 $$
这样的算法包括选择排序
参考资料
1.《算法图解》
2.《算法（第四版）》
