【C++指南】大数相加：从基础实现到性能优化
目录
问题背景
在实际编程中，我们常常会遇到需要处理大整数相加的情况。由于编程语言中基本数据类型所能表示的整数范围有限，当需要处理的整数超出这个范围时，我们就不能直接使用基本数据类型进行计算。
此时，我们可以将大整数以字符串的形式存储，通过逐位相加的方式来实现大整数的加法运算。
本文将围绕这个问题，详细介绍三种不同实现方式，从基础版逐步优化到性能更优的版本。
基础版实现
代码示例
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;
}
};
优化思路
在尾插优化版的基础上，我们进一步考虑字符串扩容的问题。
当我们使用 += 操作向字符串中添加字符时，如果字符串的容量不足，会自动进行扩容操作，而扩容操作会涉及到内存的重新分配和数据的复制，这会带来一定的性能开销。
为了避免这种情况，我们可以在开始时就使用 reserve 方法为字符串预留足够的空间，这样就可以避免多次扩容。
复杂度分析
这种实现方式的时间复杂度仍然为O（n） ，但由于减少了扩容操作，实际运行时间会更短，性能更优。
总结
通过对大数相加问题的三种不同实现方式的分析，我们可以看到，从基础版到尾插优化版再到扩容优化版，性能逐步提升。在实际编程中，我们应该根据具体情况选择合适的实现方式，同时要注意代码的性能优化，避免不必要的开销。
- 点赞
- 收藏
- 关注作者
评论（0）