I read 这一页 http://www.scala-lang.org/docu/files/collections-api/collections_40.html关于 Scala 集合的时间复杂度。正如它所说，Vector的复杂度是eC对于所有操作。
这让我想知道什么Vector是。我读了document http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.Vector它说：
由于向量在快速随机选择和快速随机函数更新之间取得了良好的平衡，因此它们是目前
不可变索引序列的默认实现。它的支持者是
分支因子为 32 的小端位映射向量 trie。
位置很好，但不连续，这对非常有好处
大序列。
与 Scala 的其他所有内容一样，它非常模糊。实际上如何Vector work?
这里的关键字是Trie。
向量被实现为Trie数据结构。
看http://en.wikipedia.org/wiki/Trie http://en.wikipedia.org/wiki/Trie.
更准确地说，它是一个“位图向量特里树”。我刚刚在这里找到了足够简洁的结构描述（以及实现 - 显然是在 Rust 中）：
https://bitbucket.org/astrieanna/bitmapped-vector-trie https://bitbucket.org/astrieanna/bitmapped-vector-trie
最相关的摘录是：
位图向量 Trie 基本上是一个 32 树。级别 1 是大小为 32 的数组，无论数据类型如何。 Level 2 是 32 个 Level 1 的数组。依此类推，直到： Level 7 是 2 个 Level 6 的数组。
UPDATE：回复赖玉轩关于复杂性的评论：
我不得不假设你在这里指的是“深度”:-D。 “eC”的图例表示“该操作实际上需要恒定的时间，但这可能取决于一些假设，例如向量的最大长度或散列键的分布。”。
如果您愿意考虑最坏的情况，并且考虑到向量的最大大小存在上限，那么我们确实可以说复杂度是恒定的。
假设我们认为最大大小为 2^32，那么这意味着无论如何，最坏的情况最多是 7 次操作。
话又说回来，我们总是可以考虑任何类型集合的最坏情况，找到一个上限，并说这是常数复杂度，但对于示例列表来说，这意味着常数为 40 亿，这不太实用。
但 Vector 恰恰相反，7 次操作超出了实际范围，这就是我们可以考虑其复杂性常数的方式在实践中.
另一种看待这个问题的方式是：我们不是在谈论 log(2,N)，而是在谈论 log(32,N)。如果你尝试绘制它，你会发现它实际上是一条水平线。因此，务实地说，随着集合的增长，您将永远无法看到处理时间的大幅增加。
是的，这仍然不是真正恒定的（这就是为什么它被标记为“eC”而不仅仅是“C”），并且您将能够看到短向量周围的差异（但同样，差异非常小，因为数字运营增长缓慢）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
