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

Question

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

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

(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)))))))) 

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

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

Я понимаю, что процедура «частичное дерево» неоднократно называют три аргумента каждый раз, когда она называется - «это-запись», «влево-дерево», и " правое дерево ctively. (А «остальное-АРМ» только тогда, когда это необходимо - либо в самом первом «частичном дереве» называют или всякий раз, когда «не-левые АППЫ» называется)

1. это-запись вызовов: автомобиль, корд, и cdr (левый результат)
2. звонки с левой стороны: машина, cdr и сама с ее длиной пополам на каждом шагу
3. правосторонние звонки: автомобиль, сам с cdr (cdr (слева)) в качестве аргумента и длина пополам

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

я запутался .. Кроме того, в части (а) на сайте решение гласит:

«в непроизводственной истекающий случае частичного дерева сначала вычисляет число элементов, которые должны быть ВНУТРИ левое поддерево сбалансированного двоичного дерева дерева, затем вызывает частичное дерево с элементами и значение , которое создает такое поддерево, а список элементов не в этом поддереве. головка неиспользуемых элементов как значение для текущего узла «

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

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

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

Chris

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) 

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

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

The this-entry является не дерево - это элемент, который расположен в узле дерева произойдет:

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

Установка

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

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

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