C++ 中字符串连接 s=s+"0" 和 s+="0" 之间的区别

Question

我想知道这两个在“时间复杂度”方面哪个更好：

for(int i=0;i<n;i++){
s=s+"0";
}

和

for(int i=0;i<n;i++){
s+="0";
}

我正在解决一个问题，在使用第一种方法时发现“TLE（时间限制超出）”，但它适用于第二种方法。

Answer 1

第一个创建一个中间字符串（将在操作s后分配+），而第二个可能不会（取决于字符串的容量）。

最坏情况下的复杂性在两种情况下都是相同的，在最好的情况下，它只是将第二种情况的新字符串复制到第一种情况的两个字符串的完整副本（+内存分配和释放）。

事实上，您的 get TLE(Time Limit Exceeded) 可能是由于这种最坏的情况一直存在，总是复制巨大的字符串，而不是仅仅向现有字符串添加一些内容（无需重新分配）。与向量一样，应该有一些启发式的方法string来提前获得足够的容量。

正如@Slava所说，这个例子应该以不同的方式编写，我想实际的代码是不同的。