SICP 2.64 порядок роста рекурсивной процедуры

Question

Я занимаюсь самообучением SICP и с трудом нахожу порядок роста рекурсивных функций.

Следующая процедура list->tree преобразует упорядоченный список в сбалансированное дерево поиска:

(define (list->tree elements) 
  (car (partial-tree elements (length elements)))) 

(define (partial-tree elts n) 
  (if (= n 0) 
      (cons '() elts) 
      (let ((left-size (quotient (- n 1) 2))) 
        (let ((left-result (partial-tree elts left-size))) 
          (let ((left-tree (car left-result)) 
                (non-left-elts (cdr left-result)) 
                (right-size (- n (+ left-size 1)))) 
            (let ((this-entry (car non-left-elts)) 
                  (right-result (partial-tree (cdr non-left-elts) 
                                              right-size))) 
              (let ((right-tree (car right-result)) 
                    (remaining-elts (cdr right-result))) 
                (cons (make-tree this-entry left-tree right-tree) 
                      remaining-elts))))))))

Я искал решение в Интернете, и следующий веб-сайт, на мой взгляд, предлагает лучшее решение, но у меня возникают трудности с его осмыслением:

http://jots-jottings.blogspot.com/2011/12/sicp-exercise-264-constructing-balanced.html

Насколько я понимаю, процедура "частичное дерево" неоднократно вызывает три аргумента каждый раз, когда она вызывается - "эта запись", "левое дерево" и "правое дерево" соответственно. (и "Остальные-Эльты" только тогда, когда это необходимо - либо в самом первом вызове "частичного дерева", либо всякий раз, когда вызывается "не-левые")

1. вызовы this-entry: car, cdr и cdr (левый результат)
2. левые входящие вызовы: car, cdr и сам по себе с каждой длиной в два раза
3. вызовы правого входа: car, сам с cdr(cdr(left-result)) в качестве аргумента и длина уменьшается вдвое

'left-entry' будет иметь базовые 2 log(n) шага, и все три аргумента будут вызывать 'left-entry' отдельно. поэтому он будет иметь троичную структуру и общее число шагов, которое я думал, будет похоже на 3^log(n). но решение говорит, что оно использует каждый индекс 1..n только один раз. Но разве "this-entry", например, не уменьшает один и тот же индекс на каждом узле отдельно от "right-entry"?

Я в замешательстве.. Далее, в части (а) сайта решения говорится:

"в не заканчивающемся случае частичное дерево сначала вычисляет количество элементов, которые должны войти в левое поддерево сбалансированного двоичного дерева размера n, затем вызывает частичное дерево с элементами и тем значением, которое оба производит такое поддерево и список элементов, не входящих в это поддерево. Затем в качестве значения для текущего узла берется заголовок неиспользуемых элементов.

Я считаю, что процедура делает эту запись перед левым деревом. Почему я не прав?

Это моя самая первая книга по CS, и мне еще не приходилось сталкиваться с основной теоремой. Это упоминается в некоторых решениях, но, надеюсь, я смогу решить вопрос, не используя его.

Спасибо за чтение, и я с нетерпением жду вашего любезного ответа,

Крис

Answer 1

Вы должны понять, как let формы работают. В

          (let ((left-tree (car left-result)) 
                (non-left-elts (cdr left-result))

left-tree ничего не "звонит". Он создается как новая лексическая переменная и ему присваивается значение (car left-result), Скобки вокруг него предназначены только для группировки элементов, описывающих одну переменную, введенную let Форма: имя переменной и ее значение:

          (let (  (   left-tree      (car left-result)  ) 
          ;;      ^^                                   ^^
                  (   non-left-elts  (cdr left-result)  )
          ;;      ^^                                   ^^

---

Вот как понять, как работает рекурсивная процедура: нет.

Только не пытайтесь понять, как это работает; вместо этого проанализируйте, что он делает, предполагая, что он делает (для меньших случаев), что он должен делать.

Вот, (partial-tree elts n) получает два аргумента: список элементов (предположительно для помещения в дерево) и длину списка. Возвращается

            (cons (make-tree this-entry left-tree right-tree) 
                  remaining-elts)

пара минусов дерева - результат преобразования, а остальные элементы, которые должны быть не оставлены, в самом верхнем вызове, если аргумент длины был правильным.

Теперь, когда мы знаем, что он должен делать, мы заглядываем внутрь. И действительно, если исходить из вышесказанного, то, что он делает, имеет смысл: вдвое сократить количество элементов, обработать список, вернуть дерево и оставшийся список (теперь не пустой), а затем обработать то, что осталось.

this-entry это не дерево - это элемент, который размещен в узле дерева:

            (let ((this-entry (car non-left-elts)) 

настройка

                  (right-size (- n (+ left-size 1))

Значит это n == right-size + 1 + left-size, Это 1 элемент, который входит в сам узел, this-entry элемент.

И поскольку каждый элемент попадает непосредственно в его узел, один раз, общее время выполнения этого алгоритма является линейным по количеству элементов во входном списке с использованием логарифмического пространства стека.