算法设计与分析

（1）包含大量的案例，通过案例分析掌握相关算法； （2）每个案例按照问题提出、问题分析、问题求解、算法实现、算法复杂性分析的思路； （3）分治法、动态规划法采用传统的类C语言伪代码进行描述；贪心算法、回溯法、分治限界法和概率算法采用C#语言实现； （4）书中对流水作业调度问题进行了深入的探讨，并给出了一组下界值估计函数。

   本书介绍计算机算法分析与设计的基本概念、典型算法和经典案例，使读者掌握常用的算法分析与设计技术。全书共分为8章，第1章介绍算法的概念与特征，算法分析与设计的相关数学基础，算法复杂性的概念、表示方法和衡量刻度标准；第2章讲述了算法相关的数据组织方式和组织结构，包括线性表、树、二叉搜索树、红黑树、B树、散列表、最小生成树等；第3～8章分别介绍分治法、动态规划法、贪心算法、回溯法、分支限界法、概率分析和随机算法等经典算法，并通过典型案例加以分析和说明。本书给出了各种算法的具体代码实现，其中，分治法、动态规划法采用传统的类C语言伪代码进行描述；贪心算法、回溯法、分支限界法、概率分析和随机算法则采用C#语言实现。

本书适合作为高等学校计算机及相关专业“算法设计与分析”课程的教材，也可供相关专业人员参考使用。

第1章算法基础/1
1.1算法概念与特征1
1.1.1算法概念1
1.1.2算法特征1
1.2数学基础1
1.2.1数学归纳法1
1.2.2取整函数3
1.2.3二项式定理5
1.2.4二项式系数6
1.2.5斐波那契数8
1.2.6生成函数8
1.3算法复杂性分析11
1.3.1算法复杂性概念11
1.3.2算法复杂性刻度标准11
1.3.3算法复杂性耗费标准12
1.3.4渐进表示12
1.3.5渐进记号的常用函数14
1.4排序算法16
1.4.1插入排序16
1.4.2希尔排序16
1.4.3选择排序17
1.4.4冒泡排序18
1.4.5合并排序19
1.4.6快速排序19
1.4.7排序算法的稳定性问题20
1.5递归与递推20
1.5.1递归20
1.5.2递推20
第2章信息结构/23
2.1线性表23
2.1.1线性表的操作23
2.1.2栈和队列24
2.1.3表的存储24
2.1.4表的操作25
2.2树26
2.2.1树的定义26
2.2.2二叉树27
2.2.3二叉树的遍历28
2.3二叉搜索树29
2.3.1二叉搜索树的建立与插入29
2.3.2二叉搜索树的删除31
2.3.3二叉搜索树的查找32
2.3.4二叉搜索树操作算法复杂度分析33
2.4红黑树33
2.4.1定义34
2.4.2红黑树性质34
2.4.3树结构的调整35
2.4.4插入35
2.4.5删除38
2.5B树40
2.5.1定义40
2.5.2B树插入操作41
2.5.3B树删除操作43
2.6散列表46
2.6.1定义46
2.6.2散列表性能分析47
2.6.3散列函数47
2.7最小生成树47
2.7.1定义47
2.7.2Kruskal算法48
2.7.3Prime算法48
第3章分治法/50
3.1概念50
3.1.1分治法的基本思想50
3.1.2分治法所处理问题的基本特征51
3.1.3分治算法的实现思路51
3.2折半查找53
3.2.1问题描述53
3.2.2问题分析53
3.2.3问题求解53
3.2.4算法实现54
3.2.5折半查找判定树55
3.2.6算法复杂度分析55
3.3顺序统计56
3.3.1问题描述56
3.3.2问题分析56
3.3.3问题求解56
3.3.4算法实现56
3.3.5算法复杂度分析58
3.4大整数乘法58
3.4.1问题描述58
3.4.2问题分析58
3.4.3分治法求解问题59
3.4.4改进的分治法59
3.5优选子数组问题59
3.5.1问题描述59
3.5.2算法分析60
3.5.3分治法求解优选子数组问题60
3.5.4算法实现60
3.5.5算法复杂性分析61
3.6矩阵乘法61
3.6.1问题描述61
3.6.2问题分析62
3.6.3分治法求解矩阵相乘62
3.6.4Strassen算法实现矩阵乘法63
3.7递归式求解63
3.7.1问题描述63
3.7.2代入法求解递归式64
3.7.3递归树法求解递归式65
3.7.4主方法求解递归式66
3.8证明主定理67
3.8.1主定理67
3.8.2主定理递归树表示67
3.8.3主定理证明68
3.9马的周游路线问题73
3.9.1问题描述73
3.9.2问题分析73
……