算法：是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。
算法分析：以算法实现占用的时间，空间等资源为主要标准，判断算法的优劣，一般占用的资源越少算法越好。
2.1数学基础
四个定义：
（1）如果存在正常数c和n0使得当N >= n0时数据结构与算法分析c语言描述，T(N)= n0时，T(N)>=cf(N),则记为T(N)=Ω(f(N))
简单理解为：T(N)的增长率大于等于f(N)
（3）如果存在T(N)=O(f(N))且T(N)=Ω(f(N))，则记为T(N)=Θ(f(N))
简单理解为：T(N)的增长率等于f(N)
（4）如果存在正常数c和n0使得当N >= n0时，T(N)
简单理解为：T(N)的增长率小于f(N)
上面四个定义比较的是函数的相对增长率，不是比较N取某值时，哪个函数值大。
（4）和（1）比较，小o就是比大O少了个等于（=）。
c和n0其实可以省略不记，是个不确定的数数据结构与算法分析c语言描述-《数据结构与算法分析--c语言描述》之第二章：算法分析，在函数比较相对增长率时，指数和低项数都要统统忽略不记。2N 和 4N2+ 2N，其实就是N和N2的比较。
法则：
  2.2模型 由于计算机有忙时、闲时，存在多线程，多进程，内存不够，缺页中断，磁盘读入等问题。造成相同的运算，在实际的计算机中不一定花费相同的时间。所以在算法分析中，定义模型，就像定义物理模型，去除一切细小的干扰，定义一个相同运算用相同时间，有无限内存的模型。
2.3 有时从磁盘读入数据所用的时间可能在数量级上比求解上述问题所需要的时间还要大，这是高效算法的典型特点。不过，数据的读入一般是个瓶颈，不能用来作为算法性能的比较标准，这个瓶颈是所有算法共同的问题。突破这个瓶颈主要靠以后计算机的性能的提高。
2.4运行时间计算
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
k++;
｝
i < N; // 算N
i++; // 算N
j = 0; // 算N
j < N; // 算N^2
j++; // 算N^2
k++; // 算N^2
精确的结果3N^2 + 3N + 1;
其实运行时间，求的是大概，完全没有必要像上面那样。
有for的一般就是N的k次方级的
有递归的一般是指数级的
有拆分的一般是对数级的
2.5最大子序列和问题
对于一个含有正数，负数的序列，求出最大的子序列和，如果序列全为正数，则和为整个序列的和，如果序列全为负数，则和为0.下面是《数据结构与算法分析--c语言描述》给出的四种算法：
（1）穷举法
<pre>int maxSubSequenceSum_1(const a[], int n) { int result = 0; int tempSum = 0; for (int i = 0; i maxLeftBorderSum) { maxLeftBorderSum = leftBorderSum; } } maxRightBorderSum = 0; rightBorderSum = 0; for (i = center+1; i maxRightBorderSum) { maxRightBorderSum = rightBorderSum; } } if (maxLeftSum > maxRightSum) { result = maxLeftSum; } else { result = maxRightSum; } if (result > maxLeftBorderSum+maxRightBorderSum) return result; else return maxLeftBorderSum+maxRightBorderSum; } int maxSubSequenceSum_3(const a[], int n) { return maxSubSum(a, 0, n-1); } </pre>
(4)效率最高的算法
<pre>int maxSubSequenceSum_4(const a[], int n) { int result = 0; int tempSum = 0; for (int i = 0; i result) { result = tempSum; } else if (tempSum 0) { temp = m % n; m = n; n = temp; } return m; } // 欧几里德递归算法 unsigned int gcd_2(unsigned int a, unsigned int b) { if (b == 0) return a; else return gcd_2(b, (a % b)); } </pre>
stein算法：
<pre>// stein算法 int Min(int a, int b) { if (a > b) return b; else return a; } int gcd_3(int a, int b) { if(a == 0) return b; if(b == 0) return a; if(a % 2 == 0 && b % 2 == 0) return 2 * gcd_3(a >> 1, b >> 1); else if(a % 2 == 0) return gcd_3(a >> 1, b); else if(b % 2 == 0) return gcd_3(a, b >> 1); else return gcd_3(abs(a - b), Min(a, b)); } </pre>
辗转相减算法：
<pre>// 辗转相减迭代算法 unsigned int gcd_4(unsigned int a, unsigned int b) { if (a == 0) return b; while (b != 0) { if (a > b) a = a - b; else b = b - a; } return a; } // 辗转相减递归算法 unsigned int gcd_5(unsigned int a, unsigned int b) { if (a == 0) return b; else return gcd_5(b, abs(a-b)); } </pre>
定理2.1：
如果M>N,则M mod N < M/2.
证明：
情况1：N M/2
则M mod N = M - N, 且2N > M, 2M - M < 2N, 2(M-N) < M, (M -N) < M/2，成立
高效率的取幂算法：
<pre>// 高效的取幂算法，用分治策略 long int pow(long int x, unsigned int n) { if (n == 0) return 1; if (n % 2 == 0) return pow(xx, n/2); else return pow(xx, n/2) * x; } </pre>
计算x62，九次乘法
x2=(x2)x
x7=(x3)2x
x15=(x7)2x
x31=(x15)2x
x62=(x31)2
练习(待解)
2.11 给出一个高效算法来确定在整数A1 < A2 < A3 ... AN的数组中是否存在整数i使得Ai=i
2.12 给出一个高效的算法
a.求最小子序列和
b.球最小的正子序列和
c.求最大子序列乘积
2.14 筛选法，计算小于N的所有素数
解答：
2.16 不用递归，写出快速求幂的程序
