【算法设计与分析】期末汇总

算法设计与分析期末汇总 算法设计基础 算法是指令的有限序列，用于解决特定问题。算法的特性包括输入、输出、有穷性、确定性、可行性、正确性、健壮性、可理解性、抽象分级和高效性。算法的描述方法有自然语言、程序流程图、伪代码和程序设计语言。 欧几里得辗转相除法是一个经典的算法，用于求自然数 m 和 n 的最大公约数。伪代码如下： 1. r = m % n; 2. 循环直到 r 等于 0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出 n; 算法的评估包括正确性、时间代价、空间代价和最优性。 算法分析 算法分析是估算时间和空间资源的过程。时间复杂性分析的关键是问题规模、基本语句和渐进符号。渐进符号包括大 O（上界）、大Ω（下界）和Θ（同时上届+下届）。 非递归算法分析的一般步骤是： 1. 建立一个代表算法运行时间的求和表达式。 2. 用渐进符号表示这个求和表达式。 递归算法分析的一般步骤是： 1. 猜测技术：对递归关系式估计一个上限，用数学归纳法证明正确性。 2. 扩展递归技术：根据递归过程建立递推关系式，然后求解该递推关系式。 判定树是一种特殊的二叉树，左子树 x≤y，右子树 x＞y。判定树的高度至少是Ω(nlog2n)。任何基于比较的排序算法，对 n 个元素进行排序的时间下界为Ω(nlog2n)。 难解问题是指不能用计算机求解的问题，如停机问题和病毒检测问题。判定问题是指回答“是”或“否”的问题。确定性算法是指每一步只有一个确定的选择的算法。非确定性算法是指猜测阶段+验证阶段的算法。 P 类问题是指可以在多项式时间内解决的问题。NP 类问题是指可以在多项式时间内验证解决的问题。NP 完全问题是指可以在多项式时间内变换为其他 NP 问题的问题。 蛮力法 蛮力法是一种设计思想，直接基于问题的描述。常见的蛮力法有顺序查找、串匹配问题、选择排序和起泡排序。 顺序查找的时间复杂性是 O(n)，可以通过增加哨兵来避免判断越界。串匹配问题可以使用 BF 算法或 KMP 算法，时间复杂性分别为 O(m*n) 和 O(n+m)。 选择排序的时间复杂性是 O(n²)，可以通过交换记录来实现。起泡排序的时间复杂性也为 O(n²)，可以通过省去最后一次扫描来改进。 组合问题包括生成排列对象、生成子集、0/1 背包问题和任务分配问题。生成排列对象的时间复杂性是 O(n!)，可以通过插入元素到已经生成的排列中来实现。生成子集的时间复杂性是 O(2^n)。