第1章  算法与性能

  1.1  算法的概念

  1.2  算法的表达

    1.2.1  自然语言

    1.2.2  结构化图形工具

    1.2.3  计算机高级语言

  1.3  算法的评价

    1.3.1  算法的正确性

    1.3.2  算法的空间复杂性

    1.3.3  算法的时间复杂性

  1.4  最差时间复杂性和平均时间复杂性

  1.5  函数的阶与渐进性分析

    1.5.1  复杂性函数的阶

    1.5.2  函数的渐进性阶的比较

    1.5.3  函数的渐进性阶的运算

    1.5.4  函数的渐进性表示与函数集合

  1.6  本章习题

第2章  递推与递归

  2.1  递推关系与递推算法

  2.2  递归函数

  2.3  递归函数的执行过程

  2.4  递归函数的时间复杂性与递归树

  2.5  估计递归函数的复杂度的主方法

  2.6  本章习题

第3章  分治法

  3.1  二分搜索算法

    3.1.1  问题分析与算法设计

    3.1.2  时间复杂性分析

  3.2  合并排序算法

    3.2.1  问题分析与算法设计

    3.2.2  Merge函数

    3.2.3  时间复杂性分析

  3.3  快速排序算法

    3.3.1  固定主元的快速排序

    3.3.2  随机选主元的快速排序

  3.4  搜索第k元

    3.4.1  平均时间为线性

    3.4.2  最差时间为线性

  3.5  最近点对

    3.5.1  一维空间中的最近点对

    3.5.2  二维空间中的最近点对

  3.6  本章习题

第4章  动态规划

  4.1  递归方法中的重复计算

  4.2  最长公共子序列

    4.2.1  问题描述

    4.2.2  递推关系分析

    4.2.3  算法实现

  4.3  最大子段和

    4.3.1  问题描述

    4.3.2  递推分析

    4.3.3  算法实现

  4.4  矩阵连乘问题

    4.4.1  问题描述

    4.4.2  递推分析

    4.4.3  算法实现

  4.5  数据压缩问题

    4.5.1  问题描述

    4.5.2  递推分析

    4.5.3  算法实现

  4.6  0-1背包问题

    4.6.1  问题描述

    4.6.2  递推分析

    4.6.3  算法描述

  4.7  消费和储蓄问题

    4.7.1  问题描述

    4.7.2  递推分析

    4.7.3  算法实现

  4.8  最优二叉搜索树问题

    4.8.1  问题描述

    4.8.2  递推分析

    4.8.3  算法实现

  4.9  本章习题

第5章  贪心算法

  5.1  活动安排问题

    5.1.1  问题描述

    5.1.2  问题分析

    5.1.3  算法实现

  5.2  服务调度问题

    5.2.1  问题描述

    5.2.2  问题分析

    5.2.3  算法实现

  5.3  最迟时间限制服务调度问题

    5.3.1  问题描述

    5.3.2  问题分析

    5.3.3  算法实现

  5.4  ε-背包问题

    5.4.1  问题描述

    5.4.2  问题分析

    5.4.3  算法实现

  5.5  最小生成树问题

    5.5.1  问题描述

    5.5.2  Prim算法原理

    5.5.3  Prim算法实现

    5.5.4  Kruskal算法原理

    5.5.5  Kruskal算法实现

  5.6  单源最短路径问题

    5.6.1  问题描述

    5.6.2  Dijkstra算法原理

    5.6.3  Dijkstra算法实现

  5.7  本章习题

第6章  深度优先搜索

  6.1  树的搜索

    6.1.1  解空间、子集树与排列树

    6.1.2  深度优先搜索

    6.1.3  0-背包问题的回溯算法

    6.1.4  n皇后问题

    6.1.5  旅行推销员问题

    6.1.6  最大团问题

    6.1.7  图着色问题

    6.1.8  连续邮资问题

  6.2  图的搜索

    6.2.1  狼羊过河问题

    6.2.2  分油问题

  6.3  本章习题

第7章  宽度优先搜索

  7.1  宽度优先搜索一般形式

    7.1.1  基本算法

    7.1.2  算法性能

    7.1.3  算法设计要素

  7.2  树的分支定界法

    7.2.1  0-1背包问题

    7.2.2  旅行推销员问题

  7.3  图的分支定界法

    7.3.1  狼羊过河问题

    7.3.2  分油问题

  7.4  本章习题

第8章  近似算法

  8.1  近似算法的概念

  8.2  0-1背包问题的0.5-近似算法

    8.2.1  贪心算法

    8.2.2  0.5-近似算法

  8.3  0-1背包问题的(1-ε)-近似算法

    8.3.1  一种动态规划算法

    8.3.2  (1-ε)-近似算法

  8.4  旅行推销员问题的2-近似算法

  8.5  本章习题

第9章  随机算法

  9.1  数值型随机算法

    9.1.1  数值积分随机算法

    9.1.2  随机计数器

  9.2  蒙特卡洛算法

    9.2.1  矩阵乘法验证

    9.2.2  质数检测

  9.3  Las Vegas算法

    9.3.1  n皇后问题

    9.3.2  通用散列算法

  9.4  本章习题

第10章  高级数据结构（一）

  10.1  线段树

    10.1.1  线段树的应用背景

    10.1.2  线段树的结构

    10.1.3  线段树的性质

    10.1.4  线段树的基本存储结构

    10.1.5  线段树的基本操作

    10.1.6  线段树的应用举例

  10.2  树状数组

    10.2.1  树状数组的应用背景

    10.2.2  树状数组的定义

    10.2.3  树状数组的实现

    10.2.4  树状数组的应用

  10.3  伸展树

    10.3.1  伸展树的应用背景

    10.3.2  伸展树的定义及特点

    10.3.3  伸展树的主要操作

  10.4

    10.4.1  概述

    10.4.2  Treap基本操作

    10.4.3  Treap的其他操作

    10.4.4  总结

  10.5  本章习题

第11章  高级数据结构（二）

  11.1  块状链表

    11.1.1  块状链表基本思想

    11.1.2  块状链表基本操作

    11.1.3  块状链表的应用

  11.2  后缀树

    11.2.1  模式匹配问题

    11.2.2  后缀树简介

    11.2.3  后缀树定义

    11.2.4  后缀树的构建

    11.2.5  后缀树的应用

  11.3  树链剖分

    11.3.1  树链剖分的思想和性质

    11.3.2  树链剖分的实现及应用

  11.4  本章习题

参考文献