Clojure库函数的时间复杂度（Big O）

Question

有没有什么资源可以列出基本的Clojure库函数（例如conj, cons等）的Big-O复杂度？我知道Big-O会根据输入类型而变化，但这样的资源是否可用？如果没有一个大致的运行速度概念的话，我编码时会感到不舒服。

- Anonymous

Answer 1

这是一张由John Jacobsen组成并从此讨论中获取的表格：

- om-nom-nom

---

“1”用引号括起来，意思是非常接近1，可以忽略不计（根据Rich Hickey的说法）。但是实际上它是O(log_32 depth)吗？ - Shannon Severance

这个表格并不完全正确。last 的时间复杂度始终为 O(n)。cons 的时间复杂度始终为 O(1)（假设 seq 的时间复杂度始终为 O(1)）。在向量中，conj 的时间复杂度只有 "1"，而不是 1。 - kotarak

@kotarak，您能否详细说明一下您的更正意见呢？ :) - Anonymous

@匿名 last 创建一个序列并遍历它。因此，O(n)。cons 只是创建一个 Cons 对象并在其第二个参数上调用 seq。因此，只要 seq 是 O(1)，cons 就是 O(1)。对向量的 conj 通常是 O(1)，但在某些情况下，必须在幕后移动数组。因此，最坏情况是 O(log32 n)，也就是 O("1")。 - kotarak

@匿名用户 还有一个更正。get方法不能用于序列。 - kotarak

我是上面表格的作者，确实那是我第一次尝试总结当时不完美的知识 - http://www.innoq.com/blog/st/2010/04/clojure_performance_guarantees.html 看起来更加明确。 - JohnJ

Answer 2

我来晚了，但是我发现第一个回答的评论中的链接更具决定性，因此我在此重新发布它，并进行了一些修改（即英语 -> big-o）：

表格Markdown源文件

在未排序的集合上，O(log₃₂n)几乎是常数时间，因为2³²个节点可以适应位分区trie节点，这意味着最坏情况下的复杂度为log₃₂2³² = 6.4。向量也是索引为键的tries。

排序集合在可能的情况下使用二分搜索。（是的，这两个技术上都是O(log n)；包括常数因子只是为了参考。）

列表保证对第一个元素的操作具有恒定时间，并对其他所有操作具有O(n)的时间复杂度。

- brymck