clojure库函数的大O.
Ano*_*ous 6 big-o clojure asymptotic-complexity
任何人都可以指向一个资源,列出基本的clojure库函数的Big-O复杂性,如conj,cons等等？我知道Big-O会根据输入的类型而有所不同,但是,这样的资源是否可用？我对编写某些东西感到不舒服,却没有大致了解它的运行速度.
om-*_*nom 16
这是John Jacobsen撰写的一张表,摘自以下讨论:
- 引号中的"1"是足够接近一个无关紧要(根据Rich Hickey.)但实际上是O(log_32深度)？ (5认同)
- 我是上表的作者,事实上这是我第一次总结我当时不完美的知识 - http://www.innoq.com/blog/st/2010/04/clojure_performance_guarantees.html看起来像是更确定. (2认同)
迟到了,但我发现第一个答案的评论中的链接更加明确,所以我在这里重新发布一些修改(即english->big-o):
在未排序的集合中,O(log 32 n)几乎是恒定的时间,并且因为2 32个节点可以适合位分区的trie节点,这意味着log 32 2 32 = 6.4的最坏情况复杂度.矢量也是索引是键的尝试.
排序集合尽可能使用二进制搜索.(是的,这些都是技术上的O(log n);包括常数因子供参考.)
列表保证第一个元素的操作时间恒定,其他所有元素的操作时间为O(n).