chars().count()时间复杂度

Question

我知道str.len()的时间复杂度是O(1)，那么chars呢？str.chars().count() O(n)还是O(1)的时间复杂度？

此外，是否有类似于Python的锈蚀时间复杂性的站点？

Answer 1

证物A

str.chars()返回一个Chars迭代器。看一下文档。少了点什么。

您会注意到，Chars没有实现ExactSizeIterator特性。如果得到的计数是O(1)，我希望它能够实现这个特性。

展览B

向下滚动到它的Iterator::count实现，我们看到：

消耗迭代器，计算迭代次数并返回它。

计算迭代次数？这可不是个好消息。

证物C

让我们来看看源代码，这是真理的最终来源。我们能找到什么？

fn count(self) -> usize {
    // length in `char` is equal to the number of non-continuation bytes
    self.iter.filter(|&&byte| !utf8_is_cont_byte(byte)).count()
}

迭代？过滤器？数数？棺材里最后的钉子。

结论

女士们先生们，我是O(n)。我放下我的案子！