算法分析与设计复习笔记_算法设计与复习笔记

第一章 算法概述

1. 算法的性质：输入、输出、确定性、有限性
2. 算法的复杂性分析：
   • 算法的渐进复杂性: T(N) - T’(N) / T(N) -> 0,就说T’(N)是T(N)当N->无穷的渐进性态。
   • f(N) = O(g(N)) : 当N >= N0时有f(N) <= Cg(N), 称函数f(N)当N充分大时有上界，g(N)是它的一个上界。 （大O相当于<=）
   • f(N) = Ω(g(N)): 当N >= N0时有f(N) >= Cg(N)，称函数f(N)当N充分大时有下界，g(N)是它的一个下界。 （大Ω相当于>=）
   • f(N) = θ(g(N)): (相当于=)

第二章 递归与分治策略

1. 分治法的设计思想：将一个难以直接解决的大问题分割成一些规模较小的相同问题，以便各个击破，分而治之。
2. 排序问题的计算时间下界为Ω(nlogn)
3. 典型例题：
   • 整数划分问题
   • Hanoi塔问题
   • 二分搜索
   • 大整数乘法
   • Strassen矩阵乘法
   • 合并排序
   • 快速排序
   • 线性时间选择
   • 循环赛日程表*

第三章 动态规划

1. 动态规划的基本思想：将待求解的问题分解成若干子问题，先求解子问题，在结合子问题的解得到原问题的解，用一个表记录所有已解决的子问题的答案。
2. 动态规划算法的基本要素
   • 最优子结构性质：问题的最优解包含其子问题的最优解
   • 重叠子问题性质
3. 动态规划算法适用于解最优化问题，设计步骤为：
   • 找出最优解的性质，刻画其结构特征
   • 递归的定义最优值
   • 自底向上的计算最优值
   • 根据计算的最优值时得到的信息构造最优解
4. 动态规划算法的变形：备忘录方法
   • 用表格保存已解决的子问题的答案，与DP不同的是，备忘录方法是自顶向下递归的
   • 备忘录方法为每个子问题建立一个记录项，初始化时存入一个特殊值，表示尚未求解。求解过程中，对于每个子问题首先查看其相应的记录项，若未求解，则计算问题的解并保存在记录项中。
5. 经典例题：
   • 矩阵连乘问题：
     m[i, j] = 0 ; i =j
     m[i, j] = min{m[i, k] + m[k + 1, j] + Pi-1PkPj} ; i < j
   • 最长公共子序列：
     c[i, j] = 0 ; i > 0, j = 0
     c[i, j] = c[i - 1, j - 1] + 1 ; i,j > 0; xi == yi
     c[i, j] = max{c[i, j - 1], c[i - 1, j]} ; i,j > 0; xi != yi
   • 最大子段和：
     b[j] = max{b[j - 1] + a[j], a[j]}; 1 <= j <= n
   • 凸多边形的最优三角剖分：
     t[i, j] = 0 ; i = j
     t[i, j] = min {t[i, k] + t[k + 1, j] + w(Vi-1 Vk Vj)} ; i < j
   • 0-1背包问题：
     m[i, j] = max{m[i + 1, j], m[i + 1, j - Wi] + Vi} ; j >= Wi
     m[i, j]= m[i + 1, j]
     m[n, j] = Vn; j >= Wn
     m[n, j] = 0 ; 0 <= j < Wn
   • 最优二叉搜索树：
     m[i, j] = Wi,j + min {m[i, k - 1] + m[k + 1, j]} ; i <= j
     m[i, i - 1] = 0 ; 1 <= i <= n

第四章 贪心算法

1. 贪心算法的基本思想：总是做出在当前看来最好的选择
2. 贪心算法的基本要素：
   • 最优子结构性质
   • 贪心选择性质：所有问题的整体最优解可以通过一系列局部最优的选择来达到。
3. 典型例题：
   • 活动安排问题：按结束时间递增排列
   • 背包问题：（背包问题可以贪心求解，而0-1背包问题不可贪心求解）
   • 最优装载问题
   • 哈夫曼编码
   • 单源最短路径：计算从源到其他各顶点的最短路径长度
     Dijkstra算法
   • 最小生成树：
     Prim算法：每次选择连通的最短的边
     Kruskal算法：每次选择最短的边，可以不连通
   • 多机调度问题：最长处理时间作业优先的贪心选择策略

第五章 回溯法

1. 回溯法的基本思想：从开始结点出发，以深度优先方式搜索整个解空间。
2. 使用两种策略避免无效搜索（剪枝函数）：
   • 用 约束函数在扩展节点处减去不满足约束的子树
   • 用限界函数减去得不到最优解的子树
3. 常见的解空间树：子集树(2^n个节点)和排列树(n!个节点)
4. 典型例题：
   • 装载问题
   • n后问题：
     用完全二叉树表示解空间，可行性约束Place减去不满足行、列和斜线约束的子树
   • 0-1背包问题
   • 图的m着色问题
   • 旅行售货员问题

第六章 分支限界法

1. 分支限界法的基本思想：以广度优先或最小耗费优先的方式搜索解空间，在每个活结点处计算一个函数值限界，根据函数值选择一个最有利的节点作为扩展节点。
2. 分类：
   • 队列式分支限界法：选择最大优先队列或最小优先队列存储活结点
   • 优先队列式分支限界法：使用最小堆存储活结点
3. 典型例题：
   • 单源最短路径问题
   • 装载问题
   • 0-1背包问题
   • 旅行售货员问题

第七章 随机化算法

1. 数值随机化算法常用语数值问题的求解，得到的往往是近似解。
2. 蒙特卡洛算法用于求问题的准确解，能求得一个解，但未必是正确的。
3. 拉斯维加斯算法不会得不到不正确的截断，一旦找到解就一定是正确的，但有时找不到解。
4. 舍伍德算法总能求得问题的一个解， 且求得的解总是正确的。