社区首页 >专栏 >【C++经典例题】大数相加：从基础实现到性能优化

【C++经典例题】大数相加：从基础实现到性能优化

倔强的石头_

发布于 2025-02-21 01:23:55

11100

代码可运行

文章被收录于专栏：C/C++指南C/C++指南

运行总次数：0

代码可运行

问题背景

在实际编程中，我们常常会遇到需要处理大整数相加的情况。由于编程语言中基本数据类型所能表示的整数范围有限，当需要处理的整数超出这个范围时，我们就不能直接使用基本数据类型进行计算。此时，我们可以将大整数以字符串的形式存储，通过逐位相加的方式来实现大整数的加法运算。本文将围绕这个问题，详细介绍三种不同实现方式，从基础版逐步优化到性能更优的版本。

基础版实现

代码示例

class Solution {
public:
    string addStrings(string num1, string num2) 
    {
        int end1 = num1.size() - 1;;//从字符串尾部遍历
        int end2 = num2.size() - 1;

        int next = 0;//进位
        string s;

        while (end1 >= 0 || end2 >= 0 )//两个字符串都遍历完成才结束
        {
            int n1 = end1 >= 0 ? num1[end1--] - '0' : 0;//先判断下标是否合法，防止越界
            int n2 = end2 >= 0 ? num2[end2--] - '0' : 0;

            int ret = n1 + n2 + next;
            next = ret / 10;
            ret = ret % 10;

            s.insert(0, 1, ret + '0');

        }

        if (next == 1)
        {
            s.insert(0, 1, '1');
        }
        return s;
    }
};

实现思路

初始化：首先，我们需要找到两个字符串的末尾位置 end1 和 end2，从这里开始逐位相加。同时，我们还需要一个变量 next 来记录进位，初始值为 0。另外，我们创建一个空字符串 s 用于存储相加的结果。
逐位相加：使用 while 循环，只要两个字符串中有一个还未遍历完，就继续循环。在每次循环中，我们先判断当前下标是否合法，如果合法则取出对应位置的数字，否则将其视为 0。然后将这两个数字与进位 next 相加，得到当前位的和 ret。接着，更新进位 next 为 ret 除以 10 的结果，ret 则取 ret 对 10 取模的结果。最后，将 ret 转换为字符并插入到字符串 s 的开头。
处理最后进位：循环结束后，我们需要检查是否还有进位，如果有则将其插入到字符串 s 的开头。

存在的问题

这种实现方式的时间复杂度较高，主要是因为在字符串 s 的开头插入字符的操作会导致字符串元素的移动，时间复杂度为O（n），其中 n是字符串的长度。因此，总的时间复杂度为 O（n²）。

尾插优化版

代码示例

class Solution {
public:
    string addStrings(string num1, string num2)
    {
        int end1 = num1.size() - 1;;//从字符串尾部遍历
        int end2 = num2.size() - 1;

        int next = 0;//进位
        string s;

        while (end1 >= 0 || end2 >= 0)//两个字符串都遍历完成才结束
        {
            int n1 = end1 >= 0 ? num1[end1--] - '0' : 0;//先判断下标是否合法，防止越界
            int n2 = end2 >= 0 ? num2[end2--] - '0' : 0;

            int ret = n1 + n2 + next;
            next = ret / 10;
            ret = ret % 10;

            s += ret + '0';//先尾插

        }

        if (next!=0)//防止丢失最后进位的数
        {
            s += next + '0';
        }
        
        reverse(s.begin(), s.end());//再反转
        return s;
    }
};

优化思路

为了避免在字符串开头插入字符带来的性能开销，我们可以采用尾插的方式：

在每次循环中，将当前位的结果字符直接添加到字符串 s 的末尾，这样时间复杂度为O（n）。循环结束后，由于结果是从低位到高位添加到字符串中的，所以我们需要将字符串反转，得到正确的顺序。

复杂度分析

这种实现方式的时间复杂度为 O（n），其中是两个字符串中较长的那个的长度。因为我们只需要遍历一次字符串，并且尾插和反转操作的时间复杂度都是O（n）。

扩容优化版

代码示例

class Solution {
public:
    string addStrings(string num1, string num2)
    {
        int end1 = num1.size() - 1;;//从字符串尾部遍历
        int end2 = num2.size() - 1;

        int next = 0;//进位

        string s;
        s.reserve(max(num1.size(), num2.size()) + 1);//直接一次扩容完成

        while (end1 >= 0 || end2 >= 0)//两个字符串都遍历完成才结束
        {
            int n1 = end1 >= 0 ? num1[end1--] - '0' : 0;//先判断下标是否合法，防止越界
            int n2 = end2 >= 0 ? num2[end2--] - '0' : 0;

            int ret = n1 + n2 + next;
            next = ret / 10;
            ret = ret % 10;

            s += ret + '0';//先尾插

        }

        if (next!=0)//防止丢失最后进位的数
        {
            s += next + '0';
        }
        
        reverse(s.begin(), s.end());//再反转
        return s;
    }
};