什么是 Clojure 操作的大 O 表现？

Question

嗨，我是 Clojure 的新手。

我见过数据结构部分有关于大 O 的描述。但在文档中有没有一个地方可以展示 Clojure 运算的所有大 O 呢？

谢谢！

Answer 1

有一些表格（来自书籍的一些）四处流传，总结了与它们操作的数据结构相关的核心操作。不幸的是，我想我们没有支持 markdown here，至少不是表格（我尝试粘贴但不起作用）。

这一个是 brymck 的来自 John Jacobsen 的原始表格（可能是从其他地方衍生出来的）。

Comments

这是一个相当好的总结。如果我要制作一个表格，我可能会专注于一个更普遍的期望桶期望——常数、亚线性或线性的。

另一个需要了解的事情是，有一些重要的接口（由谓词函数公开）也可以指向性能类别。例如，Counted（通过`counted?`检查）表示它是否可以在常数时间内计数，以及它将你在那一行看到的行为分为两类。类似地，Indexed和`indexed?`以及nth。

然后一个重要的启示是，如果一个数据结构无法在期望约束内实现一个操作，我们不会实现它。nth和count是一种特殊的例外，因为它们在这些类别之上是多态的。