本书介绍了算法的概念，算法分析的基本理论、过程和方法以及算法设计的基本策略。主要内容包括算法概述、算法效率分析基础、蛮力法、分治法、分治策略变体——减治策略和变治策略、动态规划、时空权衡技术、贪心算法、回溯法和分支限界法、NP完全性理论等。本书最后对ACM竞赛精选案例进行了分析和讲解。

　　根据教育部高等学校计算机科学与技术教学指导委员会对高等学校计算机科学与技术专业人才专业能力构成与培养的主题的阐述，计算机专业人才的专业基本能力包括计算思维能力、算法设计与分析能力、程序设计与实现能力、系统能力。算法是系统工作的基础，作为一名优秀的计算机专业人才，关键是建立算法的概念，具备算法设计与分析的能力。
本教材按照“算法基本知识—经典算法思想—算法应用实践”的顺序进行了内容的组织及编写。读者通过阅读算法基础部分，可了解算法的由来及其发展过程，理解算法的含义及问题分类，掌握算法的分析表示方法及算法效率的评价手段。面对日益复杂的问题，可将算法分为蛮力法、分治法及其变体算法、动态规划、时空权衡、贪心算法、回溯和分支限界法等几种。在经典算法思想部分，基本按照“算法思想—算法特点—算法实例—效率分析”的体例分别描述了各种算法，目的是使读者能够深入浅出地理解并掌握算法，能够分析并比较相同问题采用不同算法时的效率。为了提高读者的算法应用能力，本书结合ACM竞赛，从中选取了12个竞赛题目，例如果园篱笆问题、旅游预算问题等，并对各类问题进行了分析和讨论，加强了读者理论和实践相结合的意识。
全书共分为11章。
第1章介绍算法的概念、由来与发展，对基本问题类型、数据结构简要阐述。然后介绍算法求解的框架和步骤。
第2章介绍算法效率分析基础。介绍算法分析的框架、三种渐进符号和基本效率类型。然后介绍针对非递归算法和递归算法的数学分析方法。
第3章介绍蛮力法。它是解决问题的最直接的方法，基于问题的描述和所涉及的概念、定义直接求解。
第4章介绍分治法。分治法是问题求解采用的最常用的算法策略之一，非常重要。
第5章介绍分治策略的变体。介绍了分治法的两种变形： 减治和变治策略，并通过实例介绍这两种策略在实际中的应用。
第6章介绍动态规划算法。以实例详述动态规划的算法思想、特点和求解问题的方法步骤。
第7章介绍时空权衡技术。介绍牺牲时间效率换取空间效率和牺牲空间效率换取时间效率的算法设计方法。
第8章介绍贪心算法。它也是非常重要的算法策略，且效率较高。介绍了几种典型的采用贪心算法求解最优问题的方法。
第9章介绍搜索算法。介绍回溯法和分支限界法，这两种算法适宜解决数据量较大且难解的问题。
第10章介绍NP完全性理论。简单介绍了NP完全性理论，以引起读者进一步学习和研究的兴趣。
第11章精心挑选了12道ACM竞赛题目，对各问题进行了分析和讲解，并在电子资源中提供了程序清单，以供读者学习和参考。
本教材可以作为计算机科学与技术、软件工程、网络工程等专业本科生及研究生的教材使用，同时也可作为有关专业软件开发人员的参考书。
本教材由师智斌等编著，其中师智斌编写了第1章，
井超编写了第2、5、6章，王东编写了第3章，靳雁霞编写了第4章，梁志剑编写了第7章，雷海卫编写了第8~10章，秦品乐编写了第11章。本教材还参阅了大量国内外专家、学者发表的著作、论文，在此向这些同行们表示衷心的感谢！
由于编者水平有限，书稿虽数次修改，仍会有不妥甚至错误之处，诚盼专家和广大读者不吝指正。联系方法： 电子邮件1637350520@qq.com。

编者
2014年6月

第1章  绪论
  1.1  什么是算法
    1.1.1  算法的由来
    1.1.2  算法的发展
    1.1.3  算法的例子
  1.2  重要的问题类型
    1.2.1  排序
    1.2.2  查找
    1.2.3  字符串匹配
    1.2.4  图问题
    1.2.5  组合问题
    1.2.6  几何问题
    1.2.7  数值问题
  1.3  基本数据结构
    1.3.1  线性结构
    1.3.2  树结构
    1.3.3  图结构
    1.3.4  集合
    1.3.5  数据的物理结构
  1.4  算法问题求解基础
    1.4.1  算法求解框架
    1.4.2  算法设计步骤
  1.5  算法的表示
  1.6  为什么学习算法
  总结
  习题1
第2章  算法效率分析基础
  2.1  算法分析框架
    2.1.1  算法分析概述
    2.1.2  算法正确性分析
    2.1.3  时空效率分析
    2.1.4  算法分析过程
  2.2  渐进符号和基本效率类型
    2.2.1  三种渐进符号
    2.2.2  渐进符号的特性
    2.2.3  基本效率类型
  2.3  非递归算法的数学分析方法
  2.4  递归算法的数学分析
    2.4.1  递归算法的数学分析方法
    2.4.2  斐波那契数列
  2.5  算法的其他分析方法
  总结
  习题2
第3章  蛮力法
  3.1  概述
  3.2  排序问题
    3.2.1  选择排序
    3.2.2  冒泡排序
  3.3  查找问题
    3.3.1  顺序查找
    3.3.2  字符串匹配
  3.4  几何问题
    3.4.1  最近对问题
    3.4.2  凸包问题
  3.5  组合问题
    3.5.1  旅行商问题
    3.5.2  背包问题
  总结
  习题3
第4章  分治法
  4.1  概述
  4.2  分治法的基本策略及步骤
    4.2.1  分治法的基本策略
    4.2.2  分治法的基本步骤
  4.3  排序问题
    4.3.1  合并排序
    4.3.2  快速排序
  4.4  查找问题
    4.4.1  折半查找
    4.4.2  二叉树遍历及其相关特性
  4.5  数值计算问题
    4.5.1  大整数乘法
    4.5.2  Strassen矩阵乘法
  4.6  几何问题
    4.6.1  用分治法解最近对问题
    4.6.2  用分治法解凸包问题
  4.7  分析分治法在安排循环赛中的应用
  总结
  习题4
第5章  分治策略变体——减治策略和变治策略
  5.1  减治策略
    5.1.1  插入排序
    5.1.2  拓扑排序
    5.1.3  生成组合对象的算法
    5.1.4  减常因子算法
    5.1.5  减可变规模算法
  5.2  变治策略
    5.2.1  排序问题
    5.2.2  平衡查找树
    5.2.3  霍纳法则和二进制幂
    5.2.4  问题化简
  总结
  习题5
第6章  动态规划
  6.1  概述
  6.2  算法特点
    6.2.1  备忘录方法
    6.2.2  最优化原理
    6.2.3  求解步骤
  6.3  矩阵连乘问题
  6.4  最长公共子序列
  6.5  0-1背包问题
  6.6  最大子段和
  6.7  最优二叉查找树
  总结
  习题6
第7章  时空权衡技术
  7.1  时空权衡策略
  7.2  计数排序
  7.3  字符串匹配
  7.4  散列法
  总结
  习题7
第8章  贪心算法
  8.1  概述
    8.1.1  贪心算法的基本要素
    8.1.2  贪心算法的求解过程
  8.2  活动安排问题
  8.3  背包问题
  8.4  最小生成树问题
    8.4.1  Prim算法
    8.4.2  Kruskal算法
  8.5  单源(点)最短路径问题
  8.6  哈夫曼编码
  总结
  习题8
第9章  回溯法和分支限界法
  9.1  回溯法
    9.1.1  概述
    9.1.2  子集和问题
    9.1.3  n皇后问题
    9.1.4  哈密顿回路
    9.1.5  装载问题
  9.2  分支限界法
    9.2.1  概述
    9.2.2  0-1背包问题
    9.2.3  任务分配问题
    9.2.4  多段图的最短路径问题
    9.2.5  旅行商问题
  总结
  习题9
第10章  NP完全性理论
  10.1  判定问题和最优化问题
  10.2  P类问题
  10.3  NP类问题
  10.4  NP完全问题
  10.5  典型的NP完全问题
  10.6  其他NP完全问题
  10.7  NP完全问题的计算机处理
  总结
  习题10
第11章  案例精选
  11.1  果园篱笆问题
  11.2  空中飞行管理问题
  11.3  去数问题
  11.4  极差问题
  11.5  最优合并问题
  11.6  在棋盘中实现从初始布局到目标布局的转变
  11.7  商店购物问题
  11.8  旅游预算问题
  11.9  防卫导弹问题
  11.10  钓鱼问题
  11.11  胖男孩问题
  11.12  护卫队问题
参考文献