Примыкать-набор для упорядоченного набора представительство


Из SICP:

Упражнения 2.61

Дать реализацию из соседствовать-установить, используя заказал представление. По аналогии с элемент в набор? показать как принять преимущество заказа для производства процедурой, которая требует в среднем около половины, как много шагов, как с неупорядоченные представления.

(define (adjoin-set x set)
  (define (rec subset) 
    (cond ((null? subset) (list x))
          ((> x (car subset)) (cons (car subset) (rec (cdr subset))))
          (else (cons x subset))))
  (if (element-of-set? x set)
      set
      (rec set)))

Это может быть улучшено?



513
2
задан 21 апреля 2011 в 02:04 Источник Поделиться
Комментарии
1 ответ

Называя элемент из набора? от соседствуют-набор вводит ненужную избыточность. Можно включить этот тест в примыкают-набор функций (в вашем случае, отдых должен быть основной частью вашей функции, с = тест добавил):

(define (adjoin-set x set)
(cond
((null? set) (cons x set))
((= x (car set)) set)
((< x (car set)) (cons x set))
(else (cons (car set) (adjoin-set x (cdr set))))))

Эта функция выполняет меньше действий, поскольку он не вызывает элемент из набора?. Вместе с тем, ее сложность все-таки за o(n), который является таким же, как ваша реализация сложность, а также сложность элемента из набора?.

1
ответ дан 24 апреля 2011 в 12:04 Источник Поделиться