算法设计与分析-习题5.4

type

Post

status

Published

date

Feb 27, 2026

slug

summary

1.两个十进制n位数的积的位数范围

答案：积最少有 2n−1位，最多有 2n位。

解题思路：

1.十进制n位数的最小值是 ,最大值是。

最少位数与最多位数：

两个数都取最小值：。其中是2n-1位数。（通过有1位, 有3位可知，包含n+1位数）。
两个数都取最大值：。其中，故最多有2n位数（A介于2n位数和2n+1位数之间，且是拥有2n+1位数的十进制数的最小值，所以A最多有2n位数）。

2.用分治算法计算 2101×1130

答案：

案例：计算两个 4 位数的乘积n=4

3.a.证明等式

解题思路：利用对数换底公式和指数法则进行变形。设等式左边为，右边为。对两边取自然对数（或以任意底的对数），将不同底的对数转化为同一底，再比较即可。

3.b.为什么比更适合作为M(n)的闭合公式？

解题思路：由a知道他们二者是数学等价的，但是作为算法复杂度的闭合公式，两者表达形式的直观性和标准习惯不同。

原因分析：

4.a 为什么在大整数乘法算法的乘法次数 M(n)中，不把乘以的乘法包括进去？

答案：因为在计算机中，乘以实际上是通过左移十进制位（或二进制位）来实现的，这只需要 O(n)的加法/移位操作，而不需要真正的乘法运算。在分析大整数乘法算法（如 Karatsuba 算法）时，M(n)通常只统计非平凡的乘法（即两个非零数字块的相乘），而将乘以 10n的位移操作视为加法开销的一部分，归入递归式中的线性项 O(n)。