算法设计与分析

1.1算法的概念11.2算法的表达11.2.1自然语言11.2.2结构化图形工具21.2.3计算机高级语言31.3算法的评价31.3.1算法的正确性41.3.2算法的空间复杂性51.3.3算法的时间复杂性51.4*差时间复杂性和平均时间复杂性61.5函数的阶与渐进性分析71.5.1复杂性函数的阶71.5.2函数的渐进性阶的比较81.5.3函数的渐进性阶的运算81.5.4函数的渐进性表示与函数集合91.6本章习题9第2章递推与递归/102.1递推关系与递推算法102.2递归函数212.3递归函数的执行过程222.4递归函数的时间复杂性与递归树242.5估计递归函数的复杂度的主方法262.6本章习题27第3章分治法/293.1二分搜索算法293.1.1问题分析与算法设计293.1.2时间复杂性分析30〖1〗算法设计与分析目录[3]〖3〗3.2合并排序算法303.2.1问题分析与算法设计313.2.2merge函数313.2.3时间复杂性分析323.3快速排序算法323.3.1固定主元的快速排序323.3.2随机选主元的快速排序343.4搜索第k元353.4.1平均时间为线性363.4.2*差时间为线性373.5*近点对393.5.1一维空间中的*近点对393.5.2二维空间中的*近点对403.6本章习题44第4章动态规划/454.1递归方法中的重复计算454.2*长公共子序列474.2.1问题描述474.2.2递推关系分析474.2.3算法实现484.3*大子段和494.3.1问题描述494.3.2递推分析494.3.3算法实现504.4矩阵连乘问题514.4.1问题描述514.4.2递推分析524.4.3算法实现524.5数据压缩问题534.5.1问题描述534.5.2递推分析544.5.3算法实现554.601背包问题564.6.1问题描述564.6.2递推分析564.6.3算法描述564.7消费和储蓄问题574.7.1问题描述574.7.2递推分析584.7.3算法实现584.8*优二叉搜索树问题594.8.1问题描述594.8.2递推分析604.8.3算法实现604.9本章习题61第5章贪心算法/635.1活动安排问题645.1.1问题描述645.1.2问题分析645.1.3算法实现645.2服务调度问题655.2.1问题描述655.2.2问题分析665.2.3算法实现665.3*迟时间限制服务调度问题675.3.1问题描述675.3.2问题分析675.3.3算法实现695.4ε背包问题705.4.1问题描述705.4.2问题分析705.4.3算法实现705.5*小生成树问题725.5.1问题描述725.5.2prim算法原理725.5.3prim算法实现725.5.4kruskal算法原理745.5.5kruskal算法实现755.6单源*短路径问题775.6.1问题描述775.6.2dijkstra算法原理775.6.3dijkstra算法实现785.7本章习题80第6章深度优先搜索/816.1树的搜索816.1.1解空间、子集树与排列树816.1.2深度优先搜索826.1.301背包问题的回溯算法846.1.4n皇后问题866.1.5旅行推销员问题886.1.6*大团问题906.1.7图着色问题916.1.8连续邮资问题926.2图的搜索946.2.1狼羊过河问题956.2.2分油问题986.3本章习题100第7章宽度优先搜索/1027.1宽度优先搜索一般形式1027.1.1基本算法1027.1.2算法性能1037.1.3算法设计要素1047.2树的分支定界法1047.2.101背包问题1047.2.2旅行推销员问题1077.3图的分支定界法1097.3.1狼羊过河问题1097.3.2分油问题1127.4本章习题115第8章近似算法/1168.1近似算法的概念1168.201背包问题的0.5近似算法1178.2.1贪心算法1178.2.20.5近似算法1188.301背包问题的(1ε)近似算法1188.3.1一种动态规划算法1188.3.2(1ε)近似算法1208.4旅行推销员问题的2近似算法1218.5本章习题124第9章随机算法/1269.1数值型随机算法1269.1.1数值积分随机算法1269.1.2随机计数器1279.2蒙特卡洛算法1289.2.1矩阵乘法验证1289.2.2质数检测1299.3las vegas算法1329.3.1n皇后问题1329.3.2通用散列算法1349.4本章习题135第10章高级数据结构（一）/13610.1线段树13610.1.1线段树的应用背景13610.1.2线段树的结构13610.1.3线段树的性质13710.1.4线段树的基本存储结构13810.1.5线段树的基本操作13810.1.6线段树的应用举例14010.2树状数组14210.2.1树状数组的应用背景14210.2.2树状数组的定义14210.2.3树状数组的实现14310.2.4树状数组的应用14310.3伸展树14410.3.1伸展树的应用背景14410.3.2伸展树的定义及特点14410.3.3伸展树的主要操作14510.4treap15110.4.1概述15110.4.2treap基本操作15110.4.3treap的其他操作15310.4.4总结15510.5本章习题156第11章高级数据结构（二）/15711.1块状链表15711.1.1块状链表基本思想15711.1.2块状链表基本操作15711.1.3块状链表的应用16211.2后缀树16311.2.1模式匹配问题16311.2.2后缀树简介16311.2.3后缀树定义16311.2.4后缀树的构建16411.2.5后缀树的应用16611.3树链剖分16811.3.1树链剖分的思想和性质16811.3.2树链剖分的实现及应用16911.4本章习题177参考文献/178