2.60

练习 2.60 我们前面说明了如何将集合表示为没有重复元素的表。现在假定允许重复，例如，集合{1， 2， 3}可能被表示为表(2 3 2 1 3 2 2)。请为在这种表示上的操作设计过程 element-of-set?、adjoin-set、union-set和intersection-set。与前面不重复表示里的相应操作相比，现在各个操作的效率怎么样？在什么样的应用中你更倾向于使用这种表示，而不是前面那种无重复的表示？

element-of-set? 没有变化。

(define (element-of-set? x set)
    (cond ((null? set) #f)
        ((equal? x (car set)) #t)
        (else (element-of-set? x (cdr set)))
    )
)

(element-of-set? 1 (list 1 2 3 4))

复杂度还是 $\Theta(n)$，可能会比不重复的表示更加耗时一点，但量级是一样的。

adjoin-set

(define (adjoin-set x set) (cons x set))

(adjoin-set 1 (list 1 2 3 4))

复杂是 $\Theta(1)$，相比不重复的表示$\Theta(n)$，快多了！

union-set

和不重复的表示相比，实现上可以简化成 append，复杂度可以从 $\Theta(n^2)$ 降低成 $\Theta(n)$。

(define union-set append)

(union-set (list 1 2 3 4) (list 5 6 7 8))

intersection-set

复杂度为$\Theta(n^2)$。

(define (intersection-set set1 set2) 
    (cond 
        ((or (null? set1) (null? set2)) '())
        (
            (element-of-set? (car set1) set2) 
            (cons 
                (car set1) 
                (intersection-set (cdr set1) set2)
            )
        )
        (else (intersection-set (cdr set1) set2))
    )
)

(intersection-set (list 1 2 3 4) (list 1 2 5 8))

在存储空间廉价而时间要求很高的应用中，更倾向于使用允许重复的集合表达方式。