整数乘法的时间复杂度推导

整数乘法算法时间复杂度推导
基本乘法算法的时间复杂度
对于两个n位二进制整数A和B的标准乘法操作，传统的方法涉及逐位相乘并累加结果。此方法中，每一位都需要与其他所有位进行一次乘法运算，从而形成两层嵌套循环。
假设每个输入数字有n位，则总共需要执行大约( n \times n = n^2 )次单精度乘法[^1]。因此，简单整数乘法算法的时间复杂度为 ( O(n^2) )[^1]。
def simple_multiply(a, b):
result = 0
while b != 0:
if (b & 1):
result += a
a <<= 1
b >>= 1
return result
登录后复制
上述代码展示了如何利用移位和条件加法来模拟传统的多位数乘法规则，尽管这里展示的是基于二进制而非十进制的例子，但原理相同。每次迭代都可能增加到最终的结果上，这反映了最基础层面的乘法机制及其二次方级的增长特性。
Karatsuba快速乘法算法优化
为了减少所需的操作次数，Karatsuba提出了更高效的分治策略。该算法将较大规模的问题分解成较小子问题，并巧妙地减少了所需的乘法数量。具体来说：
给定两个长度为n的大整数X=AB和Y=CD（其中A,B,C,D均为n/2位），那么XY可以通过三个半尺寸乘积AC、BD以及(A+B)(C+D)-AC-BD得到。这样做的好处在于只需三次而不是四次完整的高维乘法即可完成整个计算过程。
这种改进使得新方案的整体效率提升至约等于 ( O(n^{log_2{3}})\approx O(n^{1.58})), 显著优于原始平方级别性能表现。