gethash
函数的时间复杂度是多少?
例如,在 c++ 中,map
的搜索时间为 O(log(n))
,而 unordered_map
的时间为 O(1)
。这两件事都写在描述中,但我找不到 Lisp 中 gethash
的任何此类引用。
实际上,这扩展到所有标准库函数。我在哪里可以找到它们的复杂性,或者我可以?谈论 sbcl,如果这很重要的话。
最佳答案
ANSI CL 标准没有指定算法复杂度的原因 库函数是它不是它的工作。该标准描述了行为,并将性能留给特定于实现的文档。 假定所有实现都将提供最佳的理论性能(否则没有人会使用它)。
要回答您的具体问题,gethash
在所有实现中都是 O(1)
。
关于algorithm - Lisp gethash 复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52681241/