方案中'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.