SICP 全笔记

Exercise 2.60. We specified that a set would be represented as a list with no duplicates. Now suppose we allow duplicates. For instance, the set {1,2,3} could be represented as the list (2 3 2 1 3 2 2). Design procedures element-of-set?, adjoin-set, union-set, and intersection-set that operate on this representation. How does the efficiency of each compare with the corresponding procedure for the non-duplicate representation? Are there applications for which you would use this representation in preference to the non-duplicate one?

效率不变。他们都需要遍历整个表:

================     ======
element-of-set?      O(n)
adjoin-set           O(n)
intersetion-set      O(n^2)
union-set            O(n^2)
================     ======

TODO