第一章
第二节 计算模型
2.4图灵机（TM）
图灵机就是作为我们分析问题的理想模型的一个案例，它由无限长的纸带，有限的字母表，有限种状态，读写头组成。
Transition Function (当前状态，当前字符；改写的目标字符，向左/向右，转入的状态)
当转入的状态为“h”，则停机。
2.5接口
当我们对图灵机做一些操作后。每次完成要把读写头复位到最初的位置停机，因为它本身以后会成为一个算法是一部分，这个算法在调用他之前有严格的规范，这种规范以后就成为大家合作时的一个准则，这种规范，更多是以 “接口” 的形式给出了，这就是“接口” 的影子。
2.6RAM
与TM模型一样，RAM模型为算法提供一个平台，在这个独立的平台上，大家有统一 的标准，对于算法的效率的评判更加可信。
在这些 模型上算法的运行时间跟其在平台上的基本操作次数程线性关系，所以我们这时可以将：T(n) = 算法在求解运算规模为n的问题时，在平台上所需的基本操作次数。
2.7 RAM实例
功能：向下取整的除法，0<= c, 1 <d;
[ c/d ] = max { x | d.x <= c }
= max { x | d.x <= c }
这里我不想把例子照抄下来，我是想让你明白：懂得问题的等价转化是多么的重要，我们拿到这个问题，大脑就是一片空白，什么都想不到。
但别人就知道如何等价转化，知道设未知数x,x是c一次一次减去d，直到小于零的次数，这个次数，就是我们要得到的整数值。
这恐怕是算法界的基本转化问题的操作，学过数学的都应该懂得转化问题的重要性，你以后要多多注意去培养这个思维，不然写程序这条路，肯定没法走下去。
也就是数学。
第三节 大O记号
3.1大O记号
1. 对于算法的复杂度，常系数项可以忽略，底次项也可以忽略，只需计入O(n^x)即可。
2. O(n)是对T(n)的最差估计，Ω(n)是对T(n)的最好估计，Θ(n)是所谓对T(n)的等效估计。
3.2复杂度
1.O(1)复杂度 （高效解）
算法不含转向（循环，调用，递归等）必顺序执行，复杂度为O(1)，但含有循环，调用，递归未必复杂度就不为O(1)这还要视具体情况而定。
2.O(log n)复杂度（高效解）
1.常底数无所谓：logb n = logb a . logan ,而logb a是无所谓的，所以常数底都是无所谓的
2.常数次幂无所谓 log n^c = c.log n = Θ(log n) 所以log内的n次幂也是无所谓的
3.对数多项式 （log n)^234+(log （n^2+n+3))^125 = Θ(log n)^234
4.复杂度为log n 的算法实际非常高效，因为从渐近的意义上讲，log n实际是无限接近于一 个常数的，也就是O(1)的，所以说它也算法高效的一个标志。
3.O(n^c)复杂度 （有效解）
多项式：
100n + 200 = O(n)
(100n - 500)(20n^2 - 300n + 2013) = O(n*n^2) = O(n^3) //看过高次项以后，之后直接抹掉底次项就是，更快的得到结果。
(2013n^2 - 20)/(1999n - 1) = O(n^2 / n) = O(n)
一般的：a n^k + a n^k-1 + ....+ an + a = O(n^k) ; a>0
线性：所有O(n)类函数
从O(n)到O(n^2) : 编程习题的主要覆盖范围
幂：((n^2013 - 24n^2003)^1/3 - 512n^567 - 1987n^122 ) = O(n^61)
4.O(2^n)（难解）
n^c = O(2^n)
n^1000 = O(1.00001^n) = O(2^n)
1.0001^n = Ω(n^1000) //可以看到，n的高次幂和2^n没有明显的分界，可以把n的高次视为指数幂的下界。
第四节 算法分析
目标即是通过之前的计算模型和大O记号来对算法进行分析两个任务：正确性 + 复杂性
4.1级数
算术级数：与末项平方同阶
T(n) = 1 + 2 + .....+ n = n(n+1)/2 = O(n^2)
幂放级数 ： 比幂次高一阶
T(n) = 1^2 + 2^2 + 3^2 + ....+ n^2 = n(n+1)(2n+1)/6 = O(n^3)
T(n) = 1^3 + 2^3 + 3^3 + ....+ n^3 = n^2(n+1)^2/4 = O(n^4)
集合级数 :于末项同阶
Ta(n) = a^0 + a^1+...+a^n = (a^n+1 - 1)/(a - 1) = O (a^n)
收敛级数
1 + 1/2 +1/2^2 + ....+ 1/n^2 < 1+ 1/2^2 = π^2/6 = O(n)
投硬币级数：（1 - λ)(1 + 2λ+3λ^2+4λ^3+...) = 1/(1 - λ) = O(1)
可能未必收敛，然而长度有限
调和级数：h(n) = 1 + 1/2 + 1/3 + ....+ 1/n = Θ（logn）
log1 + log2 + log3 + ... + logn = log (n!) = Θ (nlogn)
4.2循环
例一：
for(int i = 0; i<n ; i++)
for(int j = 0; j< n ; j++)
01Operation(i, j );
图解：
算术计数：
例二
for (i = 0; i <n ; i++)
for (j = o; j <i ; j++) //与j增长 的步长没有关系一次加2018都没关系
01Operation(i,j)；
图解：
算术级数:
例三：
for(int i = 0; i<n ; i << = 1)
for(int j = 0; j< i ; j++)
01Operation(i, j );
几何级数：
1 + 2 + 4 + 。。。+ 2^[log2(n-1)] = 2^[log2n] -1= O（n）
