clojure - clojure 库函数的大 O

Question

谁能指出我列出了基本 clojure 库函数（如 conj、cons 等）的 Big-O 复杂性的资源？我知道 Big-O 会根据输入的类型而有所不同，但是，这样的资源是否可用？如果不知道它的运行速度有多快，我会感到不舒服。

score 17 · Accepted Answer

17

这是一张由John Jacobsen撰写并取自该讨论的表格：

在此处输入图像描述

于 2013-06-11T15:42:37.393 回答

score 11 · Accepted Answer

在这里聚会迟到了，但我发现第一个答案的评论中的链接更明确，所以我在这里重新发布它并进行一些修改（即english->big-o）：

在未排序的集合上，O(log ₃₂ n) 几乎是恒定的时间，并且因为 2 ^{32 个}节点可以容纳在位分区的trie节点中，这意味着最坏情况下的复杂度为 log ₃₂ 2 ³² = 6.4。向量也是索引为键的尝试。

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

列表保证对第一个元素进行操作的恒定时间和对其他所有元素的 O(n)。

2 回答 2