算法设计与分析基础考点

第二章 算法效率分析基础 2 5 计算斐波那契数列的 O log n 算法 利用矩阵 当 n 1 时 F n 1 F n F n F n 1 0 1 1 1 n 其中的乘方运算使用霍纳法则 第三章 蛮力法 凸包问题 链接任意两点 检查剩余的点是否都在连线的同侧 效率 O n 3 分配问题 n 个任务分配给 n 个人 其中将第 j 个任务分配给第 i 个人的成本为 C i j 找 出成本最小的分配方案 蛮力法 穷举 n 种可能的方案 高效方法 匈牙利方法 第四章 分治法 主定理 对于 T n a T n b f n f n 为 n d 如果 a b d T n n log a log b 大整数乘法 a a1a0 b b1b0 其中 a 和 b 都是 n 位整数 低 n 2 位为 a0 b0 高位为 a1 b1 需要三次 n 2 位的乘法即可完成 c a b c2 10 2n c1 10 n c0 其中 c2 a1 b1 c0 a0 b0 c1 a1 a0 b1 b0 c2 c0 T n n log3 log2 最近点对问题 找到平面上 n 个点中的最近距离 先画一条竖线 将所有的点分成左右两 半 找到两部分的最近距离 d1 d2 然后考察竖线附近的点 凸包问题的快包算法 类似于快速排序 首先过最左边的点 P1 和最右边的点 Pn 将平 面分成上下两部分 然后考察上半个平面 找到距离直线 P1Pn 距离最远的点 Pmax 那么 Pmax 一定是凸包的顶点 三角形 P1PmaxPn 内部的点一定不是凸包的顶点 然后只需分 别考虑两侧的顶点即可 平均效率 O n log n 由于三角形内部的点无须考虑 甚至可以达到线性效率 最差情况 O n 2 剩下的点全都在同一侧 三角形面积的计算 三角形 x1 y1 x2 y2 x3 y3 的面积等于下面这个行列式的值的 1 2 x1 y1 1 x2 y2 1 x3 y3 1 x1y2 x2y3 x3y1 x3y2 x2y1 x1y3 第五章 减治法 插入排序 最差情况需要做 n 1 n 2 次比较 但是平均只需 n 2 2 次比较 因此胜过选择 排序和冒泡排序 插入排序有一种扩展算法 叫做 Shell 排序 拓扑排序 算法 1 通过深度优先搜索 将出栈顺序反过来即得到一个解 算法 2 先找到 一个只有出度没有入度的点 将这个点以及相关的边删除 重复此过程 生成排列 依次生成从 1 到 n 的所有排列 假设已经得到了 n 1 的所有排列 那么依次取 出 n 1 的每一个排列 将 n 插入每一个位置 按这样的顺序插入更好 对于取出的第一个 n 1 排列 从右到左插入 第二个排列从左到右插入 第三个再从右到左 例子 依次生成 1 到 3 的所有排列 开始 1 从右到左将 2 插入 1 12 21 从右到左将 3 插入 12 123 132 312 从左到右将 3 插入 21 321 231 213 依这种次序生成的排列满足最小变化要求 得到的两个相邻的排列的差别仅在于交换两个 相邻的位置 生成排列 生成 n 的所有排列 可不可以不通过 n 1 排列 而直接生成 n 的排列 并满 足最小变化要求呢 通过 Jhonson Trotter 算法 对每个元素赋予一个向左或向右的箭头 如果元素 k 指向一个相邻的较小的元素 则称 k 为移动的 JhonsonTrotter n 初始序列 1 n 所有箭头均向左 while 存在一个移动元素 k do 求最大的移动元素 k 把 k 和它指向的元素互换 调转所有大于 k 的元素的方向 输出新的排列 此算法和上面的算法生成的顺序是一样的 且都不是按字典序 生成子集 利用二进制 可否按这个顺序生成二进制串 使得两个相邻的二进制串只相差 一个比特位 也就是在子集里面要么增加了一个元素 要么删除了一个元素 答案为 是 通过二进制反射格雷码 俄式乘法 原理如下 如果 n 是偶数 那么 n m n 2 2m 否则 n m n 1 2 2m m 代码 对整数 a 和 b 相乘 result 0 while a 0 if a 2 1 result b a 2 b 2 特点 只涉及折半 加倍和相加操作 效率非常高 约瑟夫问题 n 个人围成一圈 并且从 1 到 n 编上号码 从 1 号开始 每隔一个杀掉一个 问最后剩下 几号 记幸存者的号码为 J n 那么当 n 为偶数时 也就是 n 2k J 2k 2J k 1 当 n 2k 1 时 J 2k 1 2J k 1 把 n 表示为二进制形式 并且做一次向左的循环移位 得到结果就是幸存者编号 比如 n 6 时 二进制为 110 移位后得到 101 也就是 5 号为幸存者 具体推导过程见 具体数学 插值查找 对有序数组进行查找 把数组看成是线性递增的 那么便可以直接定位到目标值附近 一般情况下 比折半查找 要快 拈游戏 两人轮流取走桌面上的棋子 每次取 1 到 m 颗 取到最后一颗的获胜 升级版 桌面上有 I 堆棋子 棋子数分别为 n1 n2 ni 玩家每次可以从任意一堆棋子中取 走任意数量的棋子 取走最后一颗棋子的人获胜 对于 I 2 的情况非常简单 略 解法 将 n1 n2 ni 表示为二进制的形式 b1 b2 bi 计算它们的二进制数位和 也就是对 每一位分别求和并忽略进位 当且仅当二进制数位和中包含至少一个 1 时 先手获胜 先 走的玩家只需保证剩下的棋子二进制数位和只包含 0 即可 Winning Ways for your Mathematical Plays 这本书包含了各种数学游戏的解法 第 6 章 变治法 预排序 用于下列场景 检验数组中元素的唯一性 查找数组中出现次数最多的元素 等 等 高斯消去法 将矩阵变成一个上三角阵 然后从最后一个方程开始 反向替换得到原方程 的解 为了减少舍入误差 每次选取第 i 列系数绝对值最大的行 并且与当前行交换 LU 分解 高斯消去法得到的上三角阵为 U 在消去过程中行的乘数构成了下三角阵 L 假 设不存在行交换的情况下 比如 在消去第 i 列的时候 把第 i 行乘以 a 加到第 j 行上 那么 U j i a 如果存在行交换的话 那么 L 也要做相应的交换 可以证明 A LU 那么方程组 Ax b 就等价于 LUx b 假设 y Ux 那么 Ly b 因为 L 是下三角阵 所以容易求出 y Ux y 所以也容易求出 x 优点 只需做一次 LU 分解 然后对所有的 b 都可以求解 计算矩阵的逆 AX I 假设逆矩阵的第 j 列为 Xj I 的第 j 列为 ej 那么原方程便等价于求 n 的方程组 A Xj ej 可通过 LU 分解来求 计算行列式 高斯消去法的每一步 要么改变行列式的符号 要么将行列式乘上一个常量 要么不变 最终得到一个上三角阵 三角阵的行列式等于对角元之积 所以容易推得原行 列式的值 AVL 树 是一棵二叉查找树 其中每个节点的平衡因子定义为该节点左右子树的高度差 这个因子要么为 0 要么为 1 或 1 注意 并不只是根节点满足这个特性 所有节点要都 满足 将一个节点插入 AVL 树 可能导致失去平衡 某些节点的平衡因子变成了 2 或 2 通过 旋转操作来回复平衡 旋转分为四种 R 右旋 L 左旋 LR 先对节点 r 的左子树左 旋 然后将以 r 为根的树右旋 RL 在插入节点后 先找到最靠近插入节点的不平衡节 点 然后旋转以该节点为根的树 2 3 树 节点分为两种 2 节点 包含 1 个元素和 2 个儿子 3 节点 包含 2 个元素和 3 个儿子 儿子可以为空 所有的叶子都必须在同一层 总是将新的键插入到叶子里 如果叶子中的键变成了 3 那么将中间的键移至父节点 并 且该叶子分裂成了两个节点 分裂过程可能一直向上进行 堆和堆排序 略 霍纳法则 对多项式 p x an x n a n 1 x n 1 a0 进行求值 也可用来进行求 幂运算 Horner p 0 n x r p n p n 为 x 的 n 次项的系数 for i n 1 i 0 i r x r p i return r 计算图中的路径数量 假设图的邻接矩阵为 A 那么 A k 中的元素 A k i j 表示了从顶点 i 到顶点 j 存在多少条长度为 k 的路径 第八章 动态规划 计算二项式系数 C n k C n 1 k 1 C n 1 k 边界 C n 0 C n n 1 Warshall 算法 计算有向图的传递闭包 也就是任意两个顶点之间是否可达 R i j k 表示 i 和 j 之间是否连通 其中中间节点在集合 1 2 k 里面 那么 R i j k R i j k 1 R i k k 1 R k j k 1 Floyd 算法 计算每对顶点之间的最短路径 思路同上 只不过把布尔值换成最短距离而 已 最优二叉查找树 给定每个 key 出现的概率 构造一棵二叉查找树 使得平均比较次数最 少 假设键值从小到大为 a1 a2 an 对应的概率分别为 p1 p1 pn 令 C i j 表示由节点 i 到 j 构成的子树中的最少查找次数 那么树根 k 一定在 i i 1 j 中 并且两棵子树都是最优 的 可以推知 C i j min C i k 1 C k