文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本文以《算法导论》Introduction to Algorithms第三版第 31 章习题 31-3「斐波那契数的三种算法」为核心逐一推导朴素递归、记忆化动态规划与 2×2 矩阵快速幂三种方法计算第 n 个斐波那契数 F_n 的正确性与运行时间并分别在加法/乘法为 O(1)的单位成本模型和加法 Θ(β)、乘法 Θ(β²)的位成本模型下核算复杂度。读完本文你将掌握用特征方程证明递归法指数级下界、用 O(n) 记忆化消除重复子问题、用矩阵幂把计算压到 O(lg n) 的完整推导并可直接复现仓库 docs/Chap31/Problems/31-3.md 中的全部解答。问题背景与两种成本模型题目要求Problem 31-3原题定义在 docs/Chap31/Problems/31-3.md并在仓库 mkdocs.yml 的导航配置中登记为第 31 章Number-Theoretic Algorithms数论算法的 Problem 31-3 Three algorithms for Fibonacci numbers。题目要求在给定 n 的前提下比较三种计算 F_n 的方法的效率共分 a–d 四问a.证明基于递推式 (3.22) 的朴素递归方法如书中第 775 页的 FIB 过程的运行时间关于 n 是指数级的b.给出用记忆化在 O(n) 时间内计算 F_n 的方法c.只用整数加法和乘法在 O(lg n) 时间内计算 F_n提示考虑矩阵 $\begin{pmatrix}0 1\\1 1\end{pmatrix}$ 及其幂d.若两个 β 位整数相加耗时 Θ(β)、相乘耗时 Θ(β²)在更合理的基本算术代价度量下重新核算三种方法的运行时间。两种成本模型成本模型加法乘法适用场景单位成本模型a–c 问O(1)O(1)理论分析的简化假设忽略数值随 n 增大而变长的效应位成本模型d 问Θ(β)Θ(β²)更接近真实计算机β 为参与运算整数的位长题目 a–c 问先假设加、减、乘两个数的代价为 O(1)与数值大小无关此时可用简单的常数系数递推刻画运行时间而 d 问要求改用更合理的代价度量即加法 Θ(β)、乘法 Θ(β²)此时必须把数字随 n 增长而不断变长这一事实计入复杂度分析。a. 朴素递归法指数级运行时间的证明递推方程的建立朴素递归算法为了求 FIB(n) 需要递归计算 FIB(n−1) 与 FIB(n−2)原解答此处笔误写为两个 FIB(n−1)按其递推式理解应为 FIB(n−2)每次递归附加以常数时间的合并于是运行时间满足$$T(n) T(n - 1) T(n - 2) \Theta(1).$$斐波那契数本身的上界为 O(2ⁿ)但这并不是紧上界需要用特征方程求出精确的指数底数。特征方程与黄金比例斐波那契递推 $F(n) F(n - 1) F(n - 2)$ 的特征方程为$$ \begin{aligned} x^2 x 1 \\ x^2 - x - 1 0, \end{aligned} $$由求根公式得到两根$x \frac{1 \pm \sqrt 5}{2}$。线性齐次递推的解具有 $F(n) \alpha_1^n \alpha_2^n$ 的形式其中 $\alpha_1, \alpha_2$ 正是特征方程的两根于是$$ \begin{aligned} F(n) \alpha_1^n \alpha_2^n \\ \bigg(\frac{1 \sqrt 5}{2}\bigg)^n \bigg(\frac{1 - \sqrt 5}{2}\bigg)^n. \end{aligned} $$由于 T(n) 与 F(n) 满足同一递推结构二者渐近相同而第二项 $\big(\frac{1 - \sqrt 5}{2}\big)^n$ 的底数 $|(1-\sqrt 5)/2| \approx 0.618 1$随 n 增大趋于 0因此$$ \begin{aligned} T(n) \bigg(\frac{1 \sqrt 5}{2}\bigg)^n \bigg(\frac{1 - \sqrt 5}{2}\bigg)^n \\ \bigg(\frac{1 \sqrt 5}{2}\bigg)^n \\ \approx O(1.618)^n. \end{aligned} $$即朴素递归法的运行时间以黄金比例 φ ≈ 1.618 为底指数增长——每一层递归产生两个规模约减 1 的子调用子问题树指数膨胀这正是指数级结论的来源。仓库佐证闭式解与多线程章节的 FIB本仓库 docs/Chap04/Problems/4-4.md 用生成函数方法独立导出了斐波那契数的闭式公式$$F_i \frac{1}{\sqrt 5}(\phi^i - \hat{\phi}^i), \quad \phi \frac{1 \sqrt 5}{2} 1.61803\ldots, \quad \hat\phi \frac{1 - \sqrt 5}{2} -0.61803\ldots$$与本题特征方程得到的 $(1 \pm \sqrt 5)/2$ 完全一致可作为本部分结论的旁证。此外书中第 775 页的 FIB 过程在仓库 docs/Chap27/27.1.md 中以多线程版本 P-FIB 的形式出现习题 27.1-3 要求画出 P-FIB(5) 的计算 DAG说明同一朴素递归结构在全书多处以不同视角被分析。b. 记忆化把指数复杂度降为线性题目要求用记忆化在 O(n) 时间内计算 F_n。本题解答明确指出这与习题 15.1-5 相同并引用该题给出的动态规划解法FIBONACCI(n) let fib[0..n] be a new array fib[0] 1 fib[1] 1 for i 2 to n fib[i] fib[i - 1] fib[i - 2] return fib[n]为什么是 O(n)朴素递归的指数级开销来自 FIB(k) 被反复重新计算记忆化无论是自顶向下的带缓存递归还是上面这种自底向上的填表保证每个子问题 F_2, F_3, …, F_n 只被计算一次每次计算只是一步 O(1) 的加法总代价为 O(n)。这正是动态规划记录已解子问题、避免重复计算的核心思想在本例中的直接体现。子问题图源自 15.1-515.1-5 进一步画出该动态规划的子问题图并统计规模顶点 $v_0, v_1, \dots, v_n$ 共 $n 1$ 个$v_0, v_1$ 各 0 条出边$v_2, v_3, \dots, v_n$ 各 2 条出边分别指向前两个子问题因此边数共 $2n - 2$ 条。子问题图呈线性链状依赖每个子问题只依赖前两个这使得一次遍历即可全部求解是 O(n) 复杂度的结构性原因。c. 矩阵快速幂O(lg n) 的对数级计算关键恒等式矩阵幂与斐波那契数的对应核心工具是矩阵 $M \begin{pmatrix}0 1\\1 1\end{pmatrix}$其 k 次幂恰好由相邻的斐波那契数构成$$ \begin{pmatrix} 0 1 \\ 1 1 \end{pmatrix}^k\begin{pmatrix} F_{k - 1} F_k \\ F_k F_{k 1} \end{pmatrix}. $$归纳证明。基例 k 1 时$M^1 \begin{pmatrix}0 1\\1 1\end{pmatrix} \begin{pmatrix}F_0 F_1\\F_1 F_2\end{pmatrix}$取 $F_0 0, F_1 1, F_2 1$成立。设 k 时恒等式成立则$$ \begin{aligned} \begin{pmatrix} 0 1 \\ 1 1 \end{pmatrix}^{k 1} \begin{pmatrix} 0 1 \\ 1 1 \end{pmatrix} \begin{pmatrix} F_{k - 1} F_k \\ F_k F_{k 1} \end{pmatrix} \\ \begin{pmatrix} F_k F_{k 1} \\ F_{k - 1} F_k F_k F_{k 1} \end{pmatrix} \\ \begin{pmatrix} F_k F_{k 1} \\ F_{k 1} F_{k 2} \end{pmatrix}. \end{aligned} $$即恒等式对 k 1 也成立原解答的推导中有一处记号笔误——右端第二个矩阵不应再带 k 次幂此处已按归纳定义修正。于是只需计算 $M^{n - 1}$其右下角元素即为 $F_n$。MATRIX-POW对指数反复平方2×2 矩阵乘法只需 8 次整数乘法和 4 次整数加法在单位成本模型下是常数时间。因此问题归结为整个算法需要执行多少次矩阵乘法。MATRIX-POW 在每一步都把指数减半MATRIX-POW(A, n) if n % 2 1 return A * MATRIX-POW(A^2, (n - 1) / 2) return MATRIX-POW(A^2, n / 2)实现时可补充递归基n 0 返回单位矩阵n 1 返回 A即可正确处理边界情形。每次递归将 n 折半且只做常数量的矩阵乘法于是递推式为$$T(n) T(n / 2) \Theta(1),$$解为 $T(n) O(\lg n)$。与模幂运算的一脉相承对指数反复平方的分治手法与第 31 章正文的 MODULAR-EXPONENTIATION 完全同构仓库 docs/Chap31/31.6.md 的习题 31.6-2 给出了按位扫描从右到左的模幂实现同样在 O(lg n) 次平方/乘法的循环内完成指数运算。将普通整数换成 2×2 矩阵就得到本题的矩阵快速幂——这是算法设计中代数结构复用的典型例子。d. 位成本模型下的真实运行时间关于 β 的约定进入 d 问前解答首先采用统一约定设参与运算的整数位长为 β并约定 β O(log n)。需要指出这是该部分全部结论成立的前提假设——由 docs/Chap04/Problems/4-4.md 的闭式解 $F_i (\phi^i - \hat\phi^i)/\sqrt 5$ 可知$F_n$ 本身的位长约 $n \lg \phi$会随 n 线性增长。因此若把 β 取为实际参与运算的数的位长就应按各递推式中 β 的实际取值重新核算本文以下结论均严格按原解答的 β O(log n) 约定陈述。(a) 朴素递归仍是指数级每次加法现在要花费 Θ(β) 时间而递归过程中参与运算的数在指数增长递推式变为$$ \begin{aligned} T(n) T(n - 1) T(n - 2) \Theta(\beta) \\ T(n - 1) T(n - 2) \Theta(\log n), \end{aligned} $$其解与原递归法相同$T(n) O\Big(\frac{1 \sqrt 5}{2}\Big)^n$。原因是 Θ(log n) 的加法代价完全被指数级的时间吸收位成本的引入不改变数量级。(b) 记忆化Θ(n log n)记忆化版本中每计算一个新值 F_i 只需做一次加法递推式变为$$M(n) M(n - 1) \Theta(\beta).$$累加求和得$$\sum_{i 2}^{n} \beta \Theta(n\beta) \Theta(2^\beta \cdot \beta),$$即在 β O(log n) 约定下为 Θ(n log n)。(c) 矩阵快速幂Θ(log³ n)每次矩阵乘法包含常数个加法与乘法递推式变为$$P(n) P(n / 2) \Theta(\beta^2),$$解为$$\Theta(\log n \cdot \beta^2) \Theta(\beta^3),$$即在 β O(log n) 约定下为 Θ(log³ n)。复杂度总览方法单位成本模型位成本模型β O(log n)a. 朴素递归Θ(φⁿ)指数级φ ≈ 1.618仍为 Θ(φⁿ)指数级b. 记忆化O(n)Θ(nβ) Θ(n log n)c. 矩阵快速幂O(lg n)Θ(log n · β²) Θ(log³ n)结论与延伸阅读三种方法代表了算法设计中三种典型的消除重复思路朴素递归不缓存、不利用结构子问题数量爆炸代价指数级记忆化以空间换时间让每个子问题只算一次代价线性矩阵快速幂则从矩阵乘法的结合律这一代数结构出发用分治平方把递归深度压到对数级。即便切换到更真实的位成本模型三者的相对优劣次序依然保持指数级的仍是指数级记忆化与矩阵法分别只需拟线性与对数立方的时间。本解答的姊妹题同样以 β 位整数运算为分析对象 docs/Chap31/Problems/31-1.md二进制 gcd 算法用减法、奇偶检验与减半替代取余与 docs/Chap31/Problems/31-2.md欧几里得算法所需位操作数的分析结论为两个 β 位输入下耗时 O(β²)共同展现了第 31 章数论算法对位复杂度的一贯关切。整个仓库以 Markdown KaTeX 编写见 README.md全部章节与习题解答的目录结构见 mkdocs.yml读者可在本地用 MkDocs 直接构建浏览。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐终极指南Pygorithm斐波那契数列三种实现方案对比——递归、记忆化与生成器终极指南Pygorithm斐波那契数列三种实现方案对比——递归、记忆化与生成器 Pygorithm是一个专注于算法学习的Python模块提供了多种数据结构和剑指Offer第10题矩阵覆盖rectCover——斐波那契数列变种的三种解法与递推推导剑指Offer第10题矩阵覆盖rectCover——斐波那契数列变种的三种解法与递推推导 本文基于 InterviewGuide 仓库中阿秀原创的《带你快教程剑指 Offer No7 斐波那契数列三种解法从递归到滚动数组附跳台阶与矩阵覆盖变种实战剑指 Offer No7 斐波那契数列三种解法从递归到滚动数组附跳台阶与矩阵覆盖变种实战 导读 本文是「带你快速刷完 67 道剑指 Offer」系列的第文档教程知识库上一篇Score Specification蓝绿部署配置降低发布风险下一篇OwlCarousel2 容器可见性检测checkVisibility属性性能影响分析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考