乐正

Actions speak louder than words.

Sicp-ex2-62

问题

请给出在集合的排序表示上union-set的一个$\Theta (n)$的实现。

解答

练习2.62 (ex2-62.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) (union-set (cdr set1) (reverse (cons (car set1) (reverse set2)))))
        (else
          (let ((x1 (car set1))
                (x2 (car set2)))
            (cond ((= x1 x2)
                   (union-set (cdr set1) set2))
                  ((< x1 x2)
                   (union-set (cdr set1) (cons x1 set2)))
                  ((< x2 x1)
                   (cons x2 (union-set set1 (cdr set2)))))))))

这面这种方式最坏的结果需要步数$\Theta (m+n)$,这也就是$\Theta (n)$的增长速度。

测试

1
2
3
4
5
(union-set '(1 3 10) '(1 2 3 4 9))
;Value 18: (1 2 3 4 9 10)

(union-set '(1 2 3 4 5 6) '(1 2 3 4 5 6 7 8))
;Value 19: (1 2 3 4 5 6 7 8)

draft

« sicp-ex2-61 sicp-ex2-63 »

Comments