第一章算法概述
1、算法的五个性质： 有穷性、确定性、能行性、输入、输出。
2、 算法的复杂性取决于：(1)求解问题的规模(N) , (2)具体的输入数据(I),( 3)算法 本身的设计(A)
，C=F(N,I,A。
3、算法的时间复杂度的上界，下界，同阶，低阶的表示。
4、 常用算法的设计技术： 分治法、动态规划法、贪心法、回溯法和分支界限法。
5、 常用的几种数据结构： 线性表、树、图。
第二章递归与分治
1、递归算法的思想：将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。 递归的
时间复杂性可归结为递归方程：
1 11= 1
T(n) <
aT(n—b) + D(n) n> 1
其中，a是子问题的个数，b是递减的步长， ~表示递减方式， D(n)是合成子问题的开销。
递归元的递减方式~有两种：1、减法，即n -b，的形式。2、除法，即n / b，的形式。
2、D(n)为常数 c：这时，T(n) = 0(n
P
)。
D(n)为线形函数cn：
r O(n) 当a. < b(N
T(n) = < Ofnlog^n) "n = bllj
I O(I1P) 二"A bl吋
其中.p = log
b
a o
D(n)为幕函数n
x
：
r O(n
x
) 当a< D(b)II J
T{ii) = O(ni1og
b
n) 'ia = D(b)ll]
.O(nr) D(b)lH
JI：中，p= log
b
ao
考虑下列递归方程：T(1) = 1
⑴ T( n) = 4T(n/2) +n
⑵ T(n) = 4T(n/2)+n
2
⑶ T(n) = 4T(n/2)+n
3
解：方程中均为a = 4，b = 2，其齐次解为n
2
。
对⑴， T a > b (D(n) = n) /• T(n) = 0(n);
对⑵，•/ a = b
2
(D(n) = n
2
) T(n) = O(n
2
iog n);
对⑶，•/ a < b
3
(D(n) = n
3
) - T(n) = 0(n
3
)；
证明一个算法的正确性需要证明两点： 1、算法的部分正确性。2、算法的终止性。
第三章贪心算法 (旅行商问题、单源最短路径问题)
以下两种算法都是为了查找最有树问题的算法：
资源评论
