C++ 中字符串 s=s+"0" 和 s+="0" 的连接区别
Difference between concat of strings s=s+"0" and s+="0" in c++
我想知道这两个"time complexity"中哪个更好：
for(int i=0;i<n;i++){
s=s+"0";
}
和
for(int i=0;i<n;i++){
s+="0";
}
我正在解决一个问题，我在使用第一种方法时发现 "TLE(Time Limit Exceed)" 但它适用于第二种方法。
第一个创建一个中间字符串（将在 + 操作后分配给 s），而第二个可能不会（取决于字符串的容量）。
两种情况下最坏情况下的复杂度是相同的，在最好情况下，它只是复制第二种情况下的新字符串，而不是第一种情况下两个字符串的完整副本（+内存分配和释放）。
你得到 TLE（超出时间限制）的事实可能是由于这种最坏的情况一直存在，总是复制巨大的字符串而不是仅仅向现有字符串添加一些内容（没有重新分配）。像vector一样，string中应该有一些启发式来提前获得足够的容量。
正如@Slava所说，这个例子应该写得不同，我想实际代码是不同的。
我知道这是一个老问题。然而对于任何其他人可能需要答案并且由于时差在比赛中解决问题非常尖锐，我想提醒一下
s = s + "0";
需要 O( len( s ) ) 操作。和
s += "0";
需要 O( 1 ).
或者如果你想在字符串的前后附加，最好使用双端队列数据结构而不是字符串。
我想知道这两个"time complexity"中哪个更好：
for(int i=0;i<n;i++){
s=s+"0";
}
和
for(int i=0;i<n;i++){
s+="0";
}
我正在解决一个问题，我在使用第一种方法时发现 "TLE(Time Limit Exceed)" 但它适用于第二种方法。
第一个创建一个中间字符串（将在 + 操作后分配给 s），而第二个可能不会（取决于字符串的容量）。
两种情况下最坏情况下的复杂度是相同的，在最好情况下，它只是复制第二种情况下的新字符串，而不是第一种情况下两个字符串的完整副本（+内存分配和释放）。
你得到 TLE（超出时间限制）的事实可能是由于这种最坏的情况一直存在，总是复制巨大的字符串而不是仅仅向现有字符串添加一些内容（没有重新分配）。像vector一样，string中应该有一些启发式来提前获得足够的容量。
正如@Slava所说，这个例子应该写得不同，我想实际代码是不同的。
我知道这是一个老问题。然而对于任何其他人可能需要答案并且由于时差在比赛中解决问题非常尖锐，我想提醒一下
s = s + "0";
需要 O( len( s ) ) 操作。和
s += "0";
需要 O( 1 ).
或者如果你想在字符串的前后附加，最好使用双端队列数据结构而不是字符串。