3
這個漂亮的函數'assoc'的時間複雜度是多少?方案中'assoc'函數的時間複雜度是多少?
這個漂亮的函數'assoc'的時間複雜度是多少?方案中'assoc'函數的時間複雜度是多少?
我假設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
。
要挑逗,m是v的大小或關聯列表中平均實際密鑰大小中的較小者。 – Svante 2009-06-23 22:31:11