算法设计与分析-习题8.3

目录1.完成本节构造最优二叉查找树的例题中余下的计算。2.a.算法OptimalBST的时间效率为什么是立方级的?b.算法 OptimalBST 的空间效率为什么是平方级的?3.写一个线性时间算法的伪代码来从根表中生成最优二叉查找树。4.请设计一种在常量时间(每个求和式)内计算求和式 ​编辑 的算法我们会在构造最优二叉查找树的动态规划算法中用到这个算法。5.判断正误一棵最优二叉查找树的根总是包含查找概率最高的键。6.如果所有键的查找概率都相等将如何对一个包含n个键的集合构造最优二叉查找树?如果n2^k平均比较次数是多少?7.a.请证明对于一个包含n个有序键的集合所能构造的不同的二叉查找树b(n)的数量满足递推关系b.已知该递推关系的解是由卡塔兰数给出的。对于n12…5验证该断言。c.求b(n)的增长次数。对于构造最优二叉查找树的穷举查找算法而言这个问题的答案意味着什么?8.设计一个Θ(n²)的算法来求最优二叉查找树。9.把求解最优二叉查找树问题的算法推广到能够处理不成功查找的情况。10.写出采用记忆功能法求解最优二叉查找树问题的伪代码。算法功能可以只限于求出一次成功查找的最少键值比较次数。11.矩阵连乘 考虑如何使得在计算n个矩阵的乘积 A₁ A₂…An时总的乘法次数最小这些矩阵的维度分别为a.给出一个三个矩阵连乘的例子当分别用(A₁A₂)A₃和A₁(A₂A₃)计算时它们的乘法次数至少相差1000倍。b.有多少种不同的方法来计算n个矩阵的连乘乘积?c.设计一个求n个矩阵乘法最优次数的动态规划算法。1.完成本节构造最优二叉查找树的例题中余下的计算。初始表计算C(1,2):因此在键A和B可能构成的两颗二叉树中最优树的根的下标是2也就是B其平均比较长度为0.4又算C(2,3)算剩下的值最终就会得到这样一个表2.a.算法OptimalBST的时间效率为什么是立方级的?最优二叉查找树动态规划算法使用三重嵌套循环第一层循环遍历子序列的长度l1~n第二层循环遍历子序列的起点i1~n-l第三层循环遍历区间 [i,j] 内所有可能的根节点 ki~j每层最多执行n 次总操作次数为n×n×nn3循环内均为常数时间操作。因此时间效率为Θ(n³)立方级。b.算法 OptimalBST 的空间效率为什么是平方级的?算法需要维护三张二维表e[i][j]最优代价表w[i][j]概率和表root[i][j]根节点表因此效率是Θ(n^2)3.写一个线性时间算法的伪代码来从根表中生成最优二叉查找树。输入 root[i][j] 根表 n 关键字总数 输出 最优二叉查找树 函数 BuildOptimalBST(root, i, j): if i j1: return 空叶子结点 // 取出最优根 k root[i][j] 创建结点 k // 递归构建左、右子树线性时间 左孩子 BuildOptimalBST(root, i, k-1) 右孩子 BuildOptimalBST(root, k1, j) return 结点 k // 主调用 调用 BuildOptimalBST(root, 1, n)4.请设计一种在常量时间(每个求和式)内计算求和式的算法我们会在构造最优二叉查找树的动态规划算法中用到这个算法。预先计算一个前缀和数组sum_p让sum_p[j]表示p1​p2​⋯pj​那么任意区间和i ~ j可以直接用减法算出,这一步是纯减法O (1) 常量时间。// 第一步预处理O(n) 时间计算前缀和数组 输入p[1..n]节点概率数组 输出前缀和数组 sum_p[0..n] sum_p[0] 0 for k from 1 to n: sum_p[k] sum_p[k-1] p[k] // 第二步任意区间求和O(1) 常量时间 函数 GetSum(i, j): return sum_p[j] - sum_p[i-1]5.判断正误一棵最优二叉查找树的根总是包含查找概率最高的键。错误最优二叉查找树的目标是最小化平均查找代价它不只取决于根结点的概率还取决于整棵树的高度与所有结点的深度。查找概率最高的键不一定是最优根因为把概率最高的键放在根可能会让左右子树非常不平衡导致其他很多结点深度变大总代价反而更高。最优二叉查找树的根是使左子树代价 右子树代价 整棵树权重和最小的那个结点不一定是概率最高的结点。6.如果所有键的查找概率都相等将如何对一个包含n个键的集合构造最优二叉查找树?如果n2^k平均比较次数是多少?此时就是完全平衡二叉查找树满二叉查找树构造方法将键按有序排列每次选取中间位置的键作为根递归对左半部分构造左子树右半部分构造右子树n2^k时比较次数约为k-1具体公式为7.a.请证明对于一个包含n个有序键的集合所能构造的不同的二叉查找树b(n)的数量满足递推关系当n0时,设 n 个有序键为 1,2,…,n。任取第k1个键作为根左子树包含前k个键有b(k)种二叉查找树。右子树包含后n−1−k个键有b(n−1−k)种二叉查找树。根可以是任意位置对所有可能的根求和空树只有 1 种故b(0)1。证毕b.已知该递推关系的解是由卡塔兰数给出的。对于n12…5验证该断言。卡特兰数公式C1​1C2​2C3​5C4​14C5​42用递推式算 b (n)b(0) 1b(1) b(0)b(0) 1b(2) b(0)b(1)b(1)b(0) 112b(3) b(0)b(2)b(1)b(1)b(2)b(0) 2125b(4) 14b(5) 42完全对应卡特兰数断言成立。c.求b(n)的增长次数。对于构造最优二叉查找树的穷举查找算法而言这个问题的答案意味着什么?约为Θ(4^n),说明穷举法完全不可行必须用动态规划8.设计一个Θ(n²)的算法来求最优二叉查找树。输入p[1..n]键的概率, n 输出最优代价 e[1][n]根表 root[1][n] 初始化 e[i][i]p[i], root[i][i]i, w[i][i]p[i] 对所有 ie[i][i-1]0, w[i][i-1]0 for l from 2 to n: // 子树长度 l2~n for i from 1 to n-l1: j i l - 1 e[i][j] ∞ w[i][j] w[i][j-1] p[j] // Knuth 优化k 只在这个区间遍历 for k from root[i][j-1] to root[i1][j]: current e[i][k-1] e[k1][j] if current e[i][j]: e[i][j] current root[i][j] k e[i][j] e[i][j] w[i][j] return e[1][n], root9.把求解最优二叉查找树问题的算法推广到能够处理不成功查找的情况。现在要加入不成功查找查不在树里的值对应虚拟叶子节点。成功查找概率p1​,p2​,...,pn​不成功查找概率q0​,q1​,...,qn​对于q对应的不存在的元素q₀比 k₁ 小q₁在 k₁~k₂ 之间…qₙ比 kₙ 大算法 OptimalBST_Full(P[1..n], Q[0..n]) // 能处理【成功查找 不成功查找】的最优二叉查找树 // 输入 // P[1..n] 成功查找概率 // Q[0..n] 不成功查找概率 // 输出最优平均代价 C[1,n]根表 R for i ← 1 to n1 do C[i, i-1] ← Q[i-1] // 改动1空树代价 Q[i-1] for i ← 1 to n do C[i, i] ← P[i] Q[i-1] Q[i] // 改动2 R[i, i] ← i for d ← 1 to n-1 do // d子树长度-1 for i ← 1 to n-d do j ← id minval ← ∞ for k ← i to j do if C[i, k-1] C[k1, j] minval minval ← C[i, k-1] C[k1, j] kmin ← k R[i, j] ← kmin // 改动3sum 必须包含 P[i..j] Q[i-1] Q[j] sum ← Q[i-1] for s ← i to j do sum ← sum P[s] sum ← sum Q[j] C[i, j] ← minval sum return C[1, n], R10.写出采用记忆功能法求解最优二叉查找树问题的伪代码。算法功能可以只限于求出一次成功查找的最少键值比较次数。算法 MemoizedOptimalBST(P[1..n]) // 记忆功能法求最优二叉查找树仅成功查找 // 输入n个键的查找概率数组 P[1..n] // 输出最优平均比较次数 C[1,n] // 第一步创建备忘录 C全部初始化为 -1表示未计算 创建二维数组 C[1..n1][0..n] for i ← 1 to n1 do for j ← 0 to n do C[i][j] ← -1 // 第二步调用递归函数 return Lookup_C(1, n) // 递归查找函数核心记忆功能 函数 Lookup_C(i, j) if C[i][j] ≠ -1 then // 已经算过直接返回记忆功能 return C[i][j] if i j then // 空树 C[i][j] ← 0 else if i j then // 单个节点 C[i][j] ← P[i] else minval ← ∞ // 枚举所有可能的根 k for k ← i to j do cost ← Lookup_C(i, k-1) Lookup_C(k1, j) if cost minval then minval ← cost // 计算 P[i] 到 P[j] 的和 sum ← 0 for s ← i to j do sum ← sum P[s] C[i][j] ← minval sum return C[i][j]11.矩阵连乘 考虑如何使得在计算n个矩阵的乘积 A₁ A₂…An时总的乘法次数最小这些矩阵的维度分别为假设所有两个矩阵的中间乘积都使用蛮力算法(基于定义)计算。a.给出一个三个矩阵连乘的例子当分别用(A₁A₂)A₃和A₁(A₂A₃)计算时它们的乘法次数至少相差1000倍。设三个矩阵维度A₁: 1 × 1000A₂: 1000 × 1A₃: 1 × 1000① 计算 (A₁A₂) A₃A₁×A₂1×1000×1 1000 次结果是 1×1 矩阵再 × A₃1×1×1000 1000 次总计2000 次② 计算 A₁(A₂A₃)A₂×A₃1000×1×1000 1,000,000 次结果是 1000×1000 矩阵再 × A₁1×1000×1000 1,000,000 次总计2,000,000 次2,000,000 ÷ 2000 1000 倍b.有多少种不同的方法来计算n个矩阵的连乘乘积?第 n-1 个卡特兰数,增长为指数级。c.设计一个求n个矩阵乘法最优次数的动态规划算法。m[i][j] 矩阵 Aᵢ 到 Aⱼ 连乘的最小乘法次数s[i][j] 最优分割位置 k递推m[i][j] min( m[i][k] m[k1][j] d[i-1]d[k]d[j] )算法 MatrixChain(d[0..n]) // 输入矩阵维度数组 d[0..n]A_i 维度 d[i-1]×d[i] // 输出最小乘法次数 m[1][n]最优分割表 s 创建 m[1..n][1..n]s[1..n][1..n] for i ← 1 to n do m[i][i] ← 0 for l ← 2 to n do // l 是矩阵链长度 for i ← 1 to n-l1 do j ← il-1 m[i][j] ← ∞ for k ← i to j-1 do cost m[i][k] m[k1][j] d[i-1]*d[k]*d[j] if cost m[i][j] then m[i][j] ← cost s[i][j] ← k return m[1][n], s