lisp - scheme中 'assoc'函数的时间复杂度是多少？

Question

这个漂亮的函数“assoc”的时间复杂度是多少？

Answer 1

我会假设 assoc 是 O(n)*，假设 equal? 在您对该函数的使用中是 O(1)。这是因为编写您自己的 assoc 版本很简单:

(define (my-assoc v lst)
  (cond ((null? lst) #f)
        ((equal? v (caar lst)) (car lst))
        (else (my-assoc v (cdr lst)))))

您可以看到这只是在列表 lst 中向下滑动，直到找到匹配项。如果未找到，则返回 #f。

* 技术上 equal? 是 O(n)，其中 n 是较小输入的大小，因此如果您使用 assoc 比较巨大的列表结构，您的运行时将是 O(n*m)，其中 n 是提供给 assoc 的列表的大小，m 是 v 的大小。