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