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