作者:随便人呐 | 来源:互联网 | 2022-12-02 20:26
功能的时间复杂度是gethash
多少?例如,在用于map
搜索的c ++中O(log(n))
,虽然unordered_map
它是O(1)
.这两件事都是用描述写的,但我gethash
在Lisp中找不到任何这样的参考.
实际上,这扩展到所有标准库函数.哪里可以找到它们的复杂性,或者我可以吗?谈论sbcl,如果重要的话.
1> sds..:
ANSI CL 标准没有指定库函数的算法复杂性的原因是它不是它的工作.该标准描述了行为,并将性能留给了特定于实现的文档.假设所有实现都将提供最佳理论性能(否则没有人会使用它).
为了回答您的具体问题,gethash
是O(1)
在所有实现.