Swift中replacingOccurrences(of:with:)方法的时间复杂度咨询

嘿，刚好我之前琢磨过这个方法的底层逻辑，虽然Apple官方文档没直接给出时间复杂度，但我们可以从Swift字符串的实现和标准库源码来推导出来：

单字符替换场景（比如你的代码示例） #

你写的myString.replacingOccurrences(of: ".", with: "")属于单字符替换，这种情况的时间复杂度是O(n)，其中n是原字符串的长度。原因很简单：

• 方法会遍历原字符串的每一个字符，这一步是O(n)
• 每次对比目标字符（这里是"."）只需要O(1)的时间
• 最后构建新字符串的过程也是线性的，因为需要把非目标字符依次拷贝进去，整体还是O(n)

多字符子串替换场景 #

如果是替换长度大于1的子串，情况会稍微复杂一点：

• 最坏情况下的时间复杂度是O(n*m)，其中n是原字符串长度，m是要替换的子串长度。这是因为在最糟的匹配场景下（比如子串是原字符串的前缀，且每个位置都需要完整对比子串的所有字符），扫描整个字符串的匹配过程会消耗O(n*m)的时间
• 不过实际中Swift标准库对字符串匹配做了不少优化（比如用了类似Boyer-Moore的高效匹配算法），大部分场景下实际运行效率会比最坏情况好很多
• 构建新字符串的过程依然是线性的，取决于原字符串长度和替换后的总长度，这部分不会超过O(n + k*l)（k是替换次数，l是替换字符串的长度），整体不会改变最坏复杂度的量级

总结 #

• 单字符替换：O(n)
• 多字符子串替换：最坏O(n*m)，实际通常更优

内容的提问来源于stack exchange，提问作者Barcenas