算法设计与分析

第 1章 算法设计基础 1
1．1算法的基本概念　2
1．2算法描述的方法　5
1．3算法设计的过程　8
1．4算法设计工具　12
1．4．1　循环设计　12
1．4．2　递归设计　16
1．4．3循环与递归的比较　17
1．5基本的数据结构　21
1．5．1　线性数据结构　21
1．5．2　树　21
1．5．3　图　22
本章小结　24
第　2章 算法效率分析基础　26
2．1　数学基础　28
2．1．1函数的渐近的界　28
2．1．2利用极限求函数的渐近的界　30
2．1．3有用的求和级数及推导方法　31
2．1．4　基本效率类型　33
2．2　算法效率分析　33
2．2．1非递归形式算法分析　33
2．2．2递归形式算法分析　35
本章小结　39
第3章　迭代法　40
3．1迭代法的设计技术　40
3．2简单迭代运算　40
3．3求解方程的近似算法　47
3．3．1非线性方程　47
3．3．2求线性代数方程组　51
本章小结　53
第4章　蛮力法　54
4．1　枚举法　54
4．2　穷举查找　59
4．3　图的搜索　63
4．3．1　深度优先查找　63
4．3．2　广度优先查找　65
本章小结　67
第5章　分治策略　68
5．1　分治法的设计技术　68
5．2　二分查找　69
5．3　大整数的乘法和Strassen矩阵乘法　70
5．4　棋盘覆盖　74
5．5　选择性问题　76
本章小结　78
第6章　回溯与分支限界　79
6．1　回溯法的设计技术　80
6．1．1　算法思想　80
6．1．2　算法框架　81
6．1．3　回溯算法的适用条件　82
6．2　回溯算法的经典例题　83
6．2．1　装载问题　83
6．2．2　n皇后问题　85
6．2．3　0-1背包问题　86
6．2．4　旅行商问题　88
6．3　分支限界法的设计技术　91
6．4　分支限界的经典例题　92
6．4．1　装载问题　92
6．4．2　背包问题　97
6．4．3　旅行商问题　101
本章小结　110
第7章　贪心算法　112
7．1　贪心算法的设计技术　112
7．2　用贪心法求问题的解　113
7．3　近似贪心问题　118
本章小结　119
第8章　动态规划　120
8．1　动态规划的设计技术　120
8．2　投资分配问题　125
8．3　背包问题　128
8．4　矩阵连乘　132
8．5　*长公共子序列　135
8．6　*大子段和　138
本章小结　140
第9章　随机算法　141
9．1同余的概念　141
9．2　随机数　143
9．3　蒙特卡罗算法　144
9．4　舍伍德算法　149
9．5　拉斯维加斯算法　151
本章小结　152