Scala的向量数据结构的时间复杂度性能如何？

Question

我知道大多数Vector方法都是有效的O(1((恒定时间(，因为它们使用的是树，但我找不到有关contains方法的任何信息。我的第一个想法是，检查所有元素必须是O(n(，但我不确定。

Answer 1

回答标题中的问题，基本操作head、tail、apply、update、prepend、append、insert的性能特征(2.13文档版本(对于Vector:都列为eC

eC操作实际上需要恒定的时间，但这可能取决于一些假设，如向量的最大长度或哈希键的分布。

您是正确的contains是O(N(，因为没有哈希或其他任何东西可以避免与所有项目进行比较。不过，如果你想确定，最好检查一下实现情况。

由于用于实现容器的许多特性和重写，在库源中找到正确的实现可能很困难，因此检查这一点的最佳方法是调试器。使用类似的代码

val v = Vector(0, 1, 2)
v.contains(1)

使用调试器进入v.contains，您将看到的源代码是：

def contains[A1 >: A](elem: A1): Boolean = exists (_ == elem)

如果你在这一点上仍然不信服，那么更多的"介入"将引导你：

def exists(p: A => Boolean): Boolean = {
var res = false
while (!res && hasNext) res = p(next())
res
}