高精度乘法

核心算法

for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    ｛
    
        c[i + j] += a[i] * b[j];
　　　｝

这段代码模拟了我们手算乘法时的过程。假设我们计算 123 × 45：
数组中的存储方式：

a[] 存储 123：a[0]=3, a[1]=2, a[2]=1
b[] 存储 45：b[0]=5, b[1]=4
c[] 用来存储结果
计算过程：
第一轮外循环 i=0：
j=0: a[0]×b[0] = 3×5 = 15 存入c[0+0]
j=1: a[0]×b[1] = 3×4 = 12 存入c[0+1]

第二轮外循环 i=1：

j=0: a[1]×b[0] = 2×5 = 10 存入c[1+0]
j=1: a[1]×b[1] = 2×4 = 8 存入c[1+1]

第三轮外循环 i=2：

j=0: a[2]×b[0] = 1×5 = 5 存入c[2+0]
j=1: a[2]×b[1] = 1×4 = 4 存入c[2+1]

最终结果 c[] 存储的就是 123 × 45 的结果：

c[0] = 15
c[1] = 12
c[2] = 5
c[3] = 4

代码实现

#include <iostream>
using namespace std;

const int N = 1e4;
int a[N], b[N], c[N];

int main() {
    string x, y;
    cin >> x >> y;
    
    int n = x.size(), m = y.size();
    for (int i = n - 1; i >= 0; i--) a[n - i - 1] = x[i] - '0';
    for (int i = m - 1; i >= 0; i--) b[m - i - 1] = y[i] - '0';
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            c[i + j] += a[i] * b[j];
    
    for (int i = 0; i < n + m - 1; i++)
        if (c[i] >= 10) {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
    
    int k = n + m - 1;
    while (k > 0 && !c[k]) k--;
    while (k >= 0) cout << c[k--];
    
    return 0;
}

时间复杂度

时间复杂度为 O(n*m)，其中 n 和 m 分别为两个数的位数。
这个循环的时间复杂度是 O(n+m)。
输出结果：时间复杂度 O(n+m)。
这里需要注意：
如果两个数字的位数相近，即 n ≈ m，那么时间复杂度可以表示为 O(n²)
这是一个比较基础的实现方式，实际上还有更快的算法（如 FFT）可以将复杂度降低到 O(nlogn)
空间复杂度为 O(n+m)，因为需要存储两个输入数组和一个结果数组

算法学习 - 高精度乘法

高精度乘法

核心算法

代码实现

时间复杂度