Анализ кода схемы для пространства и времени

Question

Я пробираюсь через онлайн-лекции MIT для классического курса 6.001: Структура и интерпретация компьютерных программ.

Я пытаюсь понять анализ сложности кода с точки зрения использования памяти и времени выполнения. В первых нескольких лекциях они представляют решение в схеме для ряда Фибоначчи.

Решение, которое они представляют в видео, имеет характеристику увеличения пространства памяти с x (производительность линейной рекурсии), что представляет большую проблему для серии Фибоначчи. Когда вы пытаетесь найти большее число Фибоначчи, пространство, необходимое для рекурсии, становится огромным.

Они предлагают попытаться найти способ получить производительность линейной итерации, когда необходимое пространство памяти остается постоянным на протяжении всего вычисления и не зависит от x.

Мое решение ниже. Мой конкретный вопрос: каков анализ производительности моего кода на схеме ниже с точки зрения использования памяти и времени выполнения?

(define (fib x)

  (define (fib-helper target total current-index i-2 i-1)
     (if (> current-index target)
            (if (= target 1)
                0
                total)
            (fib-helper target
                        (+ i-2 i-1)
                        (+ current-index 1)
                        i-1
                        (+ i-2 i-1))))

  (fib-helper x 1 3 0 1))

Answer 1

Ну, учитывая, что (fib n) вызывает n-1 вызовов на fib-helper, ваше решение работает за линейное время.fib-helper вызывает себя только один раз для каждой итерации, и каждая итерация является хвостовым вызовом, поэтому ваша программа работает в постоянном пространстве.

Это означает, что вызов (fib 1000) должен занимать только около десяти раз ЦПвремя (fib 100) при использовании того же объема памяти.

Answer 2

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

Хотя я не могу помочь вам с временем выполнения:)