重庆大学算法复习提纲.docx

《算法基础》复习提纲 基础证明设F(n)=O(f(n)) 得n1，c1满足F(n)≤c1*f(n)……设G(n)=………最终根据已知条件，证明出以下形式成立： 对于某个n3,当nn3时，F(n)+G(n)≤c3*max(f(n),g(n))成立max{f(n), g(n)} = Θ(f(n)+g(n))设M(n)= max{f(n), g(n)},则只要证明c1 (f(n)+g(n))≤ M(n)≤c2(f(n)+g(n))(n+a)b=Θ(nb)1）可从这个不等式入手：(n/2)b≤(n+a)b≤(2n)b2）直接利用Θ符号的定义证明。lim(n+a)b/ nb =递归关系式(ch4)1.替换法 :猜测解+数学归纳法证明 证明Θ时需要证明≤和≥两方面。证明O和Ω时只需证明其中一方面。2. 递归树法 见书。排序部分动态规划(ch15) 钢管切割问题：最优子结构(顶层决策)：第一刀切哪儿。递归解算法矩阵链乘法：?最优子结构(顶层决策):假设AiAi+1…Aj的最优分割点在Ak和Ak+1之间。其前子链AiAi+1…Ak和后子链Ak+1Ak+2…Aj我们可以采用与原链相同的处理方式。(最后一次乘法发生在哪里)递归解: m[i][j]表示计算矩阵Ai..Aj所需要标量乘法次数的最小值。算法最长公共子序列最优子结构(顶层决策)：A串最后一个字符与B串最后一个字符是否匹配递归解算法0-1背包:最优子结构(顶层决策)：第n个物品要不要递归解算法最优二叉有哪些信誉好的足球投注网站树最优子结构(顶层决策)：选择哪个节点作为根节点（以哪个节点为中心将所有节点分成左子树和右子树两半）递归解算法贪心算法(ch16) 分数背包：选择策略：根据每一个物品单位重量的价值vi/wi,选择单位重量价格最高。(先算性价比，然后按性价比从高到低进行选择就是了)证明 活动选择问题选择策略：选择当前剩下的活动中最早结束的。证明方式：反证法证明对于任意非空子问题Sk,令am是Sk中结束时间最早的活动，则am一定在Sk的某个最优解的集合中。（似乎可以套用在所有情况下贪心算法的证明）硬币找零问题选择策略：优先选择最大面额。证明：对于有的硬币面值集合，该贪心算法成立，对于有的硬币面值集合，该贪心算法不成立。最大流流守恒：流进等于流出 具有多个源点和多个汇点的网络最大流问题可以转化成普通的单源点、单汇点的最大流问题（通过添加一个单一的源点和一个单一的汇点并置新添加的边的容量为无穷大来达到）。 Ford-Fulkerson 算法是求最大流的一般方法，它利用了三点：残留网络、增广路径、最大流最小割定理。 残留网络：Gf 由可以容纳更多网络流的边所组成； 增广路径：为残留网络 Gf 上从 s 到 t 的一条简单路径 p，其中 p 中所的边的最小权值为该增广路径的残留容量； 最大流最小割定理：证明了 Ford-Fulkerson 算法能够得到全局最优解“当一个流是最大流，当且仅当它的残留网络不包含增广路径”。 Ford-Fulkerson 算法的简明步骤： 初始化 G 中所有边的流为 0； 计算当前图与当前流所映射的残留网络 Gf； 从残留网络上选取一条增广路径并计算出残留容量，将残留容量添加到图的当前流上； 循环步骤 b-c 直到残留网络 Gf 中不存在增广路径为止；此时的流即为 G 的最大流。