Swift中String.count的时间复杂度（BigO）是多少？

嘿，这个问题问到点子上了！很多Swift开发者在处理字符串时都会好奇这个方法的性能细节，毕竟在高频调用场景下，时间复杂度的差异影响可不小。

直接给结论：绝大多数日常使用场景中，String.count的时间复杂度是O(1)，但存在少数需要O(n)遍历计算的例外情况。

为什么大部分时候是O(1)？ #

Swift的String内部会维护一个缓存属性，用来存储当前字符串的字符计数（这里的“字符”指的是Swift定义的「扩展字形集群」，也就是我们肉眼看到的单个表意字符）。只要字符串的内容没有发生会改变字符计数的修改，这个缓存就一直有效——调用count时直接返回缓存值，完全不需要遍历整个字符串。

什么时候会变成O(n)？ #

当缓存失效的时候，count就需要遍历整个字符串重新计算字符数，这时候时间复杂度就是O(n)。常见的缓存失效场景包括：

• 首次创建某些特殊字符串时（比如从C语言字符串转换而来，或者动态生成的包含复杂组合字符的字符串）
• 对字符串进行了修改操作（比如拼接、插入、删除字符）之后的第一次count调用

不过别担心，一旦完成这次O(n)的计算，缓存会被更新，后续的count调用又会回到O(1)的速度。

举个简单例子：

• 对于普通字符串let greeting = "Hello, Swift!"，每次调用greeting.count都是直接取缓存，O(1)
• 如果我们拼接一个复杂组合字符：let modifiedGreeting = greeting + "é"（这里的é是由e和 acute accent 两个Unicode标量组合而成），第一次调用modifiedGreeting.count会遍历计算，之后再调用就直接用缓存了。

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