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))
​x
 
true

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

adjoin-set

 
(define (adjoin-set x set) (cons x set))
​
(adjoin-set 1 (list 1 2 3 4))
 
(1 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))
 
(1 2 3 4 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))
 
(1 2)

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