And*_* S. 1 lisp algorithm hashtable common-lisp
功能的时间复杂度是gethash多少？例如,在用于map搜索的c ++中O(log(n)),虽然unordered_map它是O(1).这两件事都是用描述写的,但我gethash在Lisp中找不到任何这样的参考.
gethash
map
O(log(n))
unordered_map
O(1)
实际上,这扩展到所有标准库函数.哪里可以找到它们的复杂性,或者我可以吗？谈论sbcl,如果重要的话.
sds*_*sds 8
ANSI CL 标准没有指定库函数的算法复杂性的原因是它不是它的工作.该标准描述了行为,并将性能留给了特定于实现的文档.假设所有实现都将提供最佳理论性能(否则没有人会使用它).
为了回答您的具体问题,gethash是O(1)在所有实现.
归档时间：
7 年，4 月 前
查看次数：
145 次
最近记录：