算法设计与分析

封面

版权信息

内容提要

前言

第1章 算法设计基础

1.1 算法的基本概念

1.2 算法的描述方法

1.3 算法设计的过程

1.4 算法设计工具

1.4.1 循环设计

1.4.2 递归设计

1.4.3 循环与递归的比较

1.5 基本的数据结构

1.5.1 线性数据结构

1.5.2 树

1.5.3 图

本章小结

第2章 算法效率分析基础

2.1 数学基础

2.1.1 函数的渐近的界

2.1.2 利用极限求函数的渐近的界

2.1.3 有用的求和级数及推导方法

2.1.4 基本渐近效率类型

2.2 算法效率分析

2.2.1 非递归形式算法分析

2.2.2 递归形式算法分析

2.3 关于NP问题

本章小结

第3章 迭代法

3.1 迭代法的设计技术

3.2 简单迭代运算

3.3 求解方程的近似算法

3.3.1 非线性方程

3.3.2 求线性代数方程组

本章小结

第4章 蛮力法

4.1 枚举法

4.2 穷举查找

4.3 图的搜索

4.3.1 深度优先查找

4.3.2 广度优先查找

本章小结

第5章 分治法

5.1 分治法的设计技术

5.2 二分查找

5.3 大整数的乘法和Strassen矩阵乘法

5.4 棋盘覆盖问题

5.5 选择性问题

本章小结

第6章 回溯法与分支限界法

6.1 回溯法的设计技术

6.1.1 回溯法的算法思想

6.1.2 回溯法的算法框架

6.1.3 回溯法的适用条件

6.2 回溯法的经典例题

6.2.1 装载问题

6.2.2 n皇后问题

6.2.3 0-1背包问题

6.2.4 旅行商问题

6.3 分支限界法的设计技术

6.4 分支限界法的经典例题

6.4.1 装载问题

6.4.2 背包问题

6.4.3 旅行商问题

本章小结

第7章 贪心算法

7.1 贪心算法的设计技术

7.2 用贪心算法求问题的解

7.3 近似贪心问题

本章小结

第8章 动态规划

8.1 动态规划的设计技术

8.2 投资分配问题

8.3 背包问题

8.4 矩阵连乘

8.5 最长公共子序列

8.6 最大子段和

本章小结

第9章 随机算法

9.1 同余的概念

9.2 随机数

9.3 蒙特卡罗算法

9.4 舍伍德算法

9.5 拉斯维加斯算法