时间复杂度
若存在函数 f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称 f(n) 是 T(n) 的同数量级函数。记作 T(n) = O( f(n) )，称 O( f(n) ) 为算法的渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。
OK，我们先引出官方的定义先混个眼熟。接下来看几个通俗易懂的案例：
场景1：
问：给李华一个长n寸的面包，每3天吃掉1寸，几天吃完？
答：3 X n = 3n 天。 如果用函数表达这个相对时间：T(n) = 3n
场景2：
问：给李华一个长16寸的面包，每5天吃掉面包剩余长度的一半。第一次吃掉8寸，第二次吃4寸，…… 几天可以吃得只剩1寸？
答：5 X log16 = 20天。 T(n) = 5log n
场景3：
问：给李华一个长10寸的面包和一个鸡腿，每2天吃掉1个鸡腿，几天吃完鸡腿？
答：2天 （与面包一点关系没有）。 T(n) = 2
场景4：
问：给李华一个长10寸的面包，吃掉第一个一寸需要1天时间，吃掉第二个一寸需要2天时间，吃掉第三个一寸需要3天时间…..每多吃一寸，所花的时间也多一天，几天吃完？
答：1到10的和 = 55天
1+2+3+……+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n 。 T(n) = 0.5n^2 + 0.5n
相信通过以上4个案例已经了解了： T(n) 基本操作执行次数的函数。
那么如何推导出时间复杂度呢？有如下几个原则：
- 如果运行时间是常数量级，用常数1表示；
- 只保留时间函数中的最高阶项；
- 如果最高阶项存在，则省去最高阶项前面的系数。
渐进分析（asymptotic analysis）：忽略掉那些依赖于机器的常量，不去检查实际的运行时间，而是关注运行时间的增长。
在看刚才的四个场景：
场景1： T(n) = 3n 最高阶项为3n，省去系数3，时间复杂度为：O(n)
场景2： T(n) = 5log n 最高阶项为5log n，省去系数5，时间复杂度为：O(log n)
场景3： T(n) = 2 只有常数量级，时间复杂度为：O(1)
场景4： T(n) = 0.5n^2 + 0.5n 最高阶项为0.5n^2，省去系数0.5，时间复杂度为：O(n^2)
O（1）< O（log n）< O（n）< O（n^2）
空间复杂度
空间复杂度：即程序中变量的个数
位运算
位运算在算法中很有用，速度可以比四则运算快很多。
左移 <<
10 << 1 结果： 20
左移就是将二进制全部往左移动。10的二进制：1010，左移一位：10100，十进制就是20。
基本可以把左移看作：a * (2 ^ b)
右移 >>
10 >> 1 结果： 5
右移就是将二进制全部往右移动，并去除多余的右边。右移一位：101，十进制就是5
基本可以把右移看作：a / (2 ^ b)
右移很好用，比如可以用在二分算法中取中间值
