算法设计与分析——基于C++编程语言的描述

第1章算法基础

1.1算法的基本概念

1.1.1学习算法的重要性

1.1.2算法的定义及特性

1.1.3算法的描述方式

1.1.4算法与程序的区别

1.2算法设计的一般过程

1.3算法分析

1.3.1算法分析的概念

1.3.2时间复杂性

1.3.3空间复杂性

1.3.4算法渐进复杂性

1.3.5算法复杂性的权衡考虑

1.4递归

1.4.1认知递归

1.4.2n的阶乘

1.4.3排列问题

1.4.4递归算法的复杂性分析

1.5基本数据结构

1.5.1顺序表与链表

1.5.2栈与队列

1.5.3树与图

1.5.4集合

1.6常用数学公式

1.6.1对数公式

1.6.2组合公式

1.6.3求和公式

1.6.4向下取整和向上取整公式

拓展知识： 算法界十大名师简介

本章习题

第2章贪心算法

2.1概述

2.1.1贪心算法的基本思想

2.1.2贪心算法的基本要素

2.1.3贪心算法的解题步骤及算法设计模式

2.2会场安排问题

2.3单源*短路径问题

2.4哈夫曼编码

2.5*小生成树

2.5.1Prim算法

2.5.2Kruskal算法

2.5.3两种算法的比较

拓展知识： 遗传算法

本章习题

第3章分治算法

3.1概述

3.1.1分治算法的基本思想

3.1.2分治算法的解题步骤

3.2二分查找

3.3循环赛日程表

3.4合并排序

3.5快速排序

拓展知识： 禁忌搜索算法

本章习题

第4章动态规划

4.1概述

4.1.1动态规划的基本思想

4.1.2动态规划的解题步骤

4.1.3动态规划的基本要素

4.2矩阵连乘问题

4.3凸多边形*优三角剖分问题

4.4*长公共子序列问题

4.5加工顺序问题

4.601背包问题

4.7*优二叉查找树

拓展知识： 模拟退火算法

本章习题

第5章搜索算法

5.1穷举搜索

5.2深度优先搜索

5.3回溯算法

5.3.1回溯算法的算法框架及思想

5.3.2子集树

5.3.3排列树

5.3.4满m叉树

5.4宽度优先搜索

5.5分支限界算法

5.5.1分支限界算法的基本思想

5.5.201背包问题

5.5.3旅行商问题

5.5.4布线问题

5.5.5分支限界算法与回溯算法的比较

拓展知识： 蚁群算法

本章习题

第6章随机化算法

6.1概述

6.1.1随机化算法的类型及特点

6.1.2随机数发生器

6.2数值随机化算法

6.2.1计算π值的问题及分析

6.2.2计算定积分

6.3蒙特卡罗算法

6.3.1主元素问题

6.3.2素数测试

6.4拉斯维加斯算法

6.4.1整数因子分解问题

6.4.2n皇后问题

6.5舍伍德算法

6.5.1随机快速排序

6.5.2线性时间选择问题

拓展知识： 粒子群优化算法

本章习题

第7章线性规划问题与网络流

7.1概述

7.1.1一般线性规划问题的描述

7.1.2标准型线性规划问题的描述

7.1.3标准型线性规划问题的单纯形算法

7.2*大网络流

7.2.1基本概念

7.2.2增广路算法

7.2.3*大网络流的变换与应用

7.3*小费用*大流

7.3.1基本概念

7.3.2消圈算法

7.3.3*小费用*大流的变换与应用

拓展知识： 捕食搜索算法

本章习题

第8章数论算法及计算几何算法

8.1*大公约数

8.1.1欧几里得算法

8.1.2Stein算法

8.2同余方程

8.3同余方程组

8.4线段相交

8.5凸包问题

8.5.1凸包问题的穷举搜索法

8.5.2凸包问题的分治法

8.6*接近点对问题

8.6.1*接近点对问题的穷举搜索法

8.6.2*接近点对问题的分治法

拓展知识： 动态进化算法

本章习题

第9章NP完全理论

9.1易解问题和难解问题

9.2P类问题和NP类问题

9.2.1P类问题

9.2.2NP类问题

9.2.3P类问题和NP类问题的关系

9.3NP完全问题

9.3.1多项式变换技术

9.3.2典型的NP完全问题

9.4NP完全问题的近似算法

9.4.1顶点覆盖问题

9.4.2装箱问题

9.4.3旅行商问题

9.4.4集合覆盖问题

拓展知识： DNA计算

本章习题

附录A习题解析

视频目录

Vedio Contents

视 频 名 称时长/分钟位置

算法的基本概念151.1节

算法设计的一般过程311.2节

算法分析概念及时间、空间复杂性101.3.1节

算法渐进复杂性151.3.4节

多项式时间定理证明及O的运算性质121.3.4节

算法的运行时间T(n)建立的依据201.3.4节

算法所占用的空间S（n）建立的依据71.3.4节

贪心算法的基本思想、基本要素152.1节

会场安排问题122.2节

会场安排问题算法的正确性证明112.2节

*优装载问题算法正确性证明72.2节

单源*短路径问题算法162.3节

哈夫曼编码算法182.4节

哈夫曼编码贪心算法正确性证明202.4节

哈夫曼编码C++实战132.4节

*小生成树Prim算法222.5.1节

*小生成树Kruskal算法132.5.2节

分治算法的基本思想及二分查找173.1节

循环赛日程表问题73.3节

合并排序163.4节

快速排序213.5节

动态规划的基本思想、解题步骤、基本要素304.1.1节

矩阵连乘问题164.2节

凸多边形*优三角剖分274.3节

*长公共子序列问题254.4节

加工顺序问题1274.5节

加工顺序问题294.5节

01背包问题224.6节

01背包问题的跳跃点算法224.6节

*优二叉查找树的概念144.7节

*优二叉查找树174.7节

穷举搜索与深度优先搜索135.1节

续表

视 频 名 称时长/分钟位置

回溯算法的算法框架及思想275.3.1节

子集树的概念及算法设计模式125.3.2节

01背包问题145.3.2节

01背包问题改进回溯法175.3.2节

*大团问题135.3.2节

排列树模型及算法设计模式135.3.3节

批处理作业调度问题205.3.3节

旅行商问题175.3.3节

满m叉树模型及图的m着色问题205.3.4节

*小机器重量设计问题145.3.4节

宽度优先搜索125.4节

分支限界算法及01背包问题285.5.1节

旅行商问题分支限界算法175.5.3节

布线问题分支限界算法175.5.4节

随机化算法概述及随机数发生器166.1节

数值随机化算法86.2节

蒙特卡罗算法376.3节

拉斯维加斯算法296.4节

舍伍德算法86.5节

线性规划问题227.1.1节

约束标准型线性规划问题的单纯性算法397.1.3节

两阶段单纯形算法237.1.3节

*大网络流的基本概念187.2.1节

增广路算法127.2.2节

*大网络流的变换与应用157.2.3节

*小费用*大流消圈算法157.3.2节

*大公约数238.1节

同余方程218.2节

同余方程应用——量水问题98.2节

同余方程组118.3节

线段相交188.4节

凸包问题198.5节

*接近点对问题258.6节

P类问题和NP类问题169.2节

NP完全问题119.3节

NP完全问题的近似算法179.4节