关于 string

灌水区

happy_zero @ 2024-11-25 21:31:19

求问：string 类型的 + 和 += 分别是什么复杂度的？s=s+"a" 和 `s+="a" 的复杂度是 O(|S|) 还是 O(1)？

我之前好像有看到过后面那种是 O(1) 的，但网上搜了好像是 O(n) 的，不确定来问一下。

by zhantaiming2014 @ 2024-11-25 21:32:34

@happy_zero

1.不知道

2.O(1)

by shy_lihui @ 2024-11-25 21:32:43

@happy_zero s+="a" O(1)，s=s+a o(n)

by shy_lihui @ 2024-11-25 21:33:25

@happy_zero s+="a"等同于s.append("a")

by ny_Dacong @ 2024-11-25 21:33:49

@happy_zero

见http://oi-wiki.com/contest/common-mistakes/#%E4%BC%9A%E5%AF%BC%E8%87%B4-tle中，“使用 + 运算符向 std::string 类字符串追加字符”一项

by TheShuMo @ 2024-11-25 21:44:25

@happy_zero

s=s+a 是建立一个 string s+a 再复制 O(n)

而 s+=a 是在末尾追加 O(1)

大概吧

by happy_zero @ 2024-11-25 21:53:52

@TheShuMo@ny_Dacong@liruizhou_lihui@zhantaiming0504 谢谢！（wssb，只看了 oi-wiki 中 string 的部分）