作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
本文将详细介绍解决LeetCode题目43 "字符串相乘"的三种方法：模拟乘法手算、Karatsuba算法，以及快速傅立叶变换（FFT）方法。这些方法逐渐提升计算大数乘法的效率。
问题描述
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1: 输入: num1 = "2", num2 = "3" 输出: "6" 示例 2: 输入: num1 = "123", num2 = "456" 输出: "56088"
方法一：模拟乘法手算
解题步骤
- 初始化结果数组：长度为两数长度之和，用于存放乘积的每一位。
- 逐位相乘：外层和内层循环分别遍历两个字符串的每一位数字，相乘后加到结果数组的相应位置。
- 处理进位：从结果数组的末尾开始向前处理进位。
- 输出结果：将结果数组转换为字符串，注意去除前导零。
代码示例
def multiply(num1: str, num2: str) -> str: if num1 == "0" or num2 == "0": return "0" m, n = len(num1), len(num2) # 结果数组，长度为m+n，最大位数的情况 result = [0] * (m + n) # 从后向前遍历两个数字 for i in range(m-1, -1, -1): for j in range(n-1, -1, -1): # 两数对应位相乘，并加上之前该位的累积结果 mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0')) # 求和位置，即数组中对应的索引 p1, p2 = i + j, i + j + 1 # 总和 sum = mul + result[p2] # 设置当前位和进位 result[p1] += sum // 10 result[p2] = sum % 10 # 将结果数组转换为字符串，首先去除数组前端的0 while len(result) > 1 and result[0] == 0: result.pop(0) return ''.join(map(str, result))
算法分析
- 时间复杂度: O(M*N), 其中 M 和 N 是输入数字的长度。
- 空间复杂度: O(M+N), 用于存储计算结果。
方法二：Karatsuba 算法
解题步骤
Karatsuba 算法是一种分治算法，它通过将大数运算分解为较小数的运算来减少乘法操作的总数。这种方法利用了数学上的巧妙技巧来加速大整数的乘法过程。
- 分割数字：将每个数分割成两部分，例如，将数字123456分割为123和456，分割点通常在中间，或者靠近中间。
- 递归计算：
- 设两个大数为 ( a ) 和 ( b )，分别分割为 ( a1, a0 ) 和 ( b1, b0 )，其中 ( a1, b1 ) 是高位部分，( a0, b0 ) 是低位部分。
- 计算三个关键乘积：
- ( p1 = a1 * b1 )
- ( p2 = a0 * b0 )
- ( p3 = (a1 + a0) * (b1 + b0) )
- 结果通过组合这三个乘积获得：( result = p1 * 10^2m + (p3 - p1 - p2) * 10^m + p2 )，其中 ( m ) 是分割的位数。
- 合并结果：根据上述公式组合得到最终的乘积。
完整的规范代码
def karatsuba(num1, num2): if len(num1) < 10 or len(num2) < 10: # 为简化计算，小于10位数直接转为整数计算 return str(int(num1) * int(num2)) # 将输入数字补齐为等长 max_len = max(len(num1), len(num2)) num1 = num1.zfill(max_len) num2 = num2.zfill(max_len) # 计算分割位数 half_len = max_len // 2 # 高位和低位数 high1, low1 = num1[:-half_len], num1[-half_len:] high2, low2 = num2[:-half_len], num2[-half_len:] # 递归计算p1, p2, p3 z0 = karatsuba(low1, low2) z1 = karatsuba(str(int(low1) + int(high1)), str(int(low2) + int(high2))) z2 = karatsuba(high1, high2) # 组合结果 result = str(int(z2) * 10**(2*half_len) + (int(z1) - int(z2) - int(z0)) * 10**half_len + int(z0)) return result # 示例调用 print(karatsuba("123456789", "987654321")) # 输出: "121932631112635269"
算法分析
- 时间复杂度: (O(n^1.585，其中 ( n ) 是输入数字的位数。这比传统的 (O(n^2)) 方法要快。
- 空间复杂度: (O(log n))，主要空间消耗在递归调用栈上。
优点
- 效率提升：对于大数乘法，Karatsuba算法提供了显著的速度优势。
- 适用于大数：非常适合处理大规模数字，常用于计算机科学和大数据领域。
缺点
- 实现复杂度：相比简单的逐位乘法，Karatsuba算法实现更为复杂，特别是在处理数字分割和递归方面。
- 边界处理：在实际实现时，处理数字长度和递归的终止条件需要小心设计。
Karatsuba算法是大数乘法的一个有效优
化方法，尤其适合于需要快速乘法计算的应用，如加密和数值模拟。通过利用数学的分治技巧，它能够有效地减少计算复杂度，提升计算性能。
方法三：快速傅立叶变换（FFT）
解题步骤
快速傅立叶变换（FFT）是一种高效的数字乘法方法，适用于大数乘法。其基本思想是将整数乘法转换为多项式乘法问题，利用FFT快速进行点值计算。
- 数位扩展与对齐：首先将数字字符串转换为逆序的整数数组，并扩展长度至2的幂次方，以满足FFT的要求。
- 应用FFT转换：将数字数组通过FFT转换到频域，即计算其点值表示。
- 点值乘法：将两个数的点值数组对应位置相乘，这相当于多项式乘法的点值表示。
- 逆FFT变换：应用逆FFT将乘积的点值表示转换回系数表示，即得到时间域的多项式系数。
- 处理进位与格式化：将逆FFT的结果处理进位，然后转换为字符串输出。
完整的规范代码
使用numpy库来实现FFT和逆FFT，这里假设已经安装了numpy。
import numpy as np def fft(a): n = len(a) if n == 1: return a even = fft(a[0::2]) odd = fft(a[1::2]) T = [np.exp(-2j * np.pi * k / n) * odd[k] for k in range(n // 2)] return [even[k] + T[k] for k in range(n // 2)] + [even[k] - T[k] for k in range(n // 2)] def ifft(a): n = len(a) if n == 1: return a even = ifft(a[0::2]) odd = ifft(a[1::2]) T = [np.exp(2j * np.pi * k / n) * odd[k] for k in range(n // 2)] return [(even[k] + T[k]) / 2 for k in range(n // 2)] + [(even[k] - T[k]) / 2 for k in range(n // 2)] def multiply(num1, num2): n = 1 while n < max(len(num1), len(num2)): n <<= 1 n <<= 1 a = np.array([int(x) for x in num1[::-1]] + [0] * (n - len(num1)), dtype=complex) b = np.array([int(x) for x in num2[::-1]] + [0] * (n - len(num2)), dtype=complex) fa = fft(a) fb = fft(b) fc = fa * fb c = ifft(fc) result = [0] * n carry = 0 for i in range(n): result[i] = int(np.round(c[i].real)) + carry carry = result[i] // 10 result[i] %= 10 while len(result) > 1 and result[-1] == 0: result.pop() return ''.join(map(str, result[::-1])) # 示例调用 print(multiply("123456789", "987654321")) # 输出: "121932631112635269"
算法分析
- 时间复杂度：(O(n log n))，其中 (n) 是结果数字的最大长度。这得益于FFT和逆FFT的效率，它们将多项式乘法的复杂度从 (O(n^2)) 降至 (O(n log n))。
- 空间复杂度：(O(n))，主要用于存储数字数组及其变换结果。
优点
- 极高效：对于大规模数字运算，FFT比传统算法和Karatsuba算法更高效。
- 广泛应用：FFT在科学计算和工程领域中有广泛应用，特别是在信号处理方面。
缺点
- 实现复杂度：FFT算法比起简单的乘法算法要复杂，需要处理复数运算和逆变换。
- 依赖外部库：为了高效实现FFT，通常依赖于专门的数学库，如 numpy。
此FFT方法适用于需要快速处理非常大的数字乘法的场景，例如在数据加密、大数科学计算中非常有用。
结论
为了直观地比较解决LeetCode题目43 "字符串相乘"的三种方法，下面的表格将展示它们在不同技术维度的性能和特点，包括时间复杂度、空间复杂度以及各自的优势和劣势。
| 特征 | 方法一：模拟乘法手算 | 方法二：Karatsuba算法 | 方法三：FFT乘法 |
| 时间复杂度 | O(M*N) | O(N^1.585) | O(N log N) |
| 空间复杂度 | O(M+N) | O(N) | O(N) |
| 优势 | - 直观且易于实现 - 不需要复杂的数学背景 |
- 快于传统方法 - 分治方法减少乘法次数 |
- 最快的方法，适用于非常大的数 - 有效利用FFT算法加速计算 |
| 劣势 | - 时间复杂度高 - 对于非常大的数字效率低 |
- 实现相对复杂 - 对初学者不友好 |
- 实现复杂，需要数学背景知识 - 依赖外部数学库如numpy |
| 适用场景 | - 小到中等规模的数字 - 教学和简单应用 |
- 大数字乘法 - 需要快速算法但又不至于用FFT |
- 大规模数字计算 - 科学计算和工程应用 |
综合分析
方法一（模拟乘法手算）：
- 这种方法非常直观，模拟了人们在纸上进行乘法运算的过程。
- 它最适合于数字规模较小（例如数位不超过几百）的场景。
- 对于大规模数字（如数千位或更多），计算效率会显著降低。
方法二（Karatsuba 算法）：
- Karatsuba 算法通过分治技术提高了乘法的效率，适合中到大规模的数字乘法。
- 虽然它比模拟乘法快，但在极大规模数字乘法（例如数万位）场景下，仍可能不够高效。
方法三（FFT乘法）：
- FFT 乘法提供了最优的时间复杂度，特别适合于大规模数位的乘法问题，如在密码学或大规模科学计算中常见。
- FFT 的主要缺点是实现复杂性高，需要较强的数学背景支持，并且在某些实现中需要依赖专业的数学库。
在实际选择算法时，应考虑具体的应用需求、数字的规模以及可用资源（如是否可以使用外部库）。对于日常应用和教学，模拟乘法或Karatsuba算法通常足够用；而在需要处理非常大规模数字的科学计算中，FFT 算法是最佳选择。
欢迎关注微信公众号 数据分析螺丝钉
