Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
11 lines (7 sloc) 501 Bytes

本题将集合表示为可以有重复元素的表,那么

  • element-of-set?intersection-set都不用变
  • union-setadjoin-set不再需要比较,直接把两个set合并起来即可。

union-set的时间复杂度从O(n2)变为了O(n)

adjoin-set的时间复杂度从O(n)变为了O(1)

很明显,我们这里采用了空间换时间的方式。 其次,如果我们能的数据集本身就很少有重复的,那么用这种方式也是比较好的。