Rust中str.chars().count()的时间复杂度是O(n)还是O(1)？有对应查询站点吗？

1. chars方法及count()的时间复杂度 #

Rust的字符串类型str底层是UTF-8编码的动态长度字节序列，str.len()返回的是预存储的字节总长度，所以确实是O(1)复杂度。

• str.chars()方法本身的复杂度为O(1)：它只是创建一个绑定了原字符串指针、起始/结束偏移量的迭代器结构体，不会遍历字符串内容。
• str.chars().count()的复杂度为O(n)（n为字符串的字节长度）：因为UTF-8编码中单个字符的长度从1字节到4字节不等，Rust不会预存字符串的字符总数，count()操作需要逐字节扫描判断字符边界，统计总字符数，所以耗时和字符串长度线性相关。

其他常见chars迭代器操作的时间复杂度：

• 单次next()调用：O(1)，仅需计算当前位置的字符长度，移动指针即可
• nth(k)：O(k)，需要依次跳过前k个字符才能定位目标，无法通过固定偏移量直接寻址
• last()：O(1)，仅需要从字符串末尾向前扫描最多3个字节就能定位到最后一个字符的起始位置，耗时和字符串总长度无关

2. Rust时间复杂度查询渠道 #

Rust标准库的官方文档中，每个方法的说明部分都会明确标注对应的时间复杂度，你可以直接查询对应方法的文档获取权威信息，目前没有和Python社区的时间复杂度汇总页完全一致的第三方汇总站点。

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