clojure操作的big O是什么？

Question

您好，我对clojure还不太熟悉。

我看到在数据结构部分有一些big O。但是，有没有文档可以展示clojure操作的所有big O呢？

谢谢！

Answer 1

有几张表格（也来自书籍）流传开来，总结了一些与数据结构相关的核心操作。不幸的是，我认为我们这里不支持Markdown，至少不支持表格（我尝试粘贴，但不起作用）。

这是brymck的 John Jacobsen的原始表格（可能来自其他地方）。

Comments

这是一份相当不错的摘要。如果我要做一个表格，我可能会关注几个期望桶，这些桶更为通用——常量、亚线性或线性。

还需要知道的是，有一些重要的接口（由谓词函数暴露）暗示了性能类别。例如，Counted（通过`counted?`检查）表明它是否可以在常数时间内计数，并且这把你在那一行看到的行为分成两个部分。同样，Indexed和`indexed?`以及nth。

然后，一个重要的启示是，如果一个数据结构无法在期望约束内实现操作，则我们不实现它。nth和count有点特殊，因为它们在上面的这些类别中是泛型的。