Какова временная сложность этой функции возведения в степень Схемы?

Question

Какова сложность времени? Почему?

(define (mult a b)
      (define (internal a accum)
        (if (= a 1) accum
            (internal (- a 1) (+ accum b))))
      (internal a b))

(define (to-the-power-of m n)
  (define (internal x accum)
    (if (= x 0) accum
        (internal (- x 1) (mult accum m))))
  (internal n 1))

Answer 1

временную сложность для мульт части можно найти так:

для вычисления (mult a b), (внутренний a aa) вызывается, пока a = 1 таким образом, у нас есть некоторая хвостовая рекурсия (цикл), которая повторяется по.

мы, таким образом, знаем, что временная сложность (mult a b) равна O (a) (= линейная временная сложность)

(к мощности m n) также имеет определение (внутренний х накопитель), которое также циклично (до x = 0)

так что снова у нас есть O (x) (= линейная сложность по времени)

Но : мы не учли время, необходимое для вызовов функций внутренних ...
Во внутренней части мы используем определение (mult a b), которое является линейным по временной сложности, поэтому мы имеем следующий случай: в первой итерации mult вызывается с помощью: (mult 1 m) -> O (1)
вторая итерация это становится: (мульт м м) -> O (м)
третья итерация: (м² м²) -> O (м * м) и так далее Понятно, что это растет, пока n = 0 (или во внутреннем не станет x = 0)

Таким образом, мы можем сказать, что сложность времени будет зависеть от m и n: O (m ^ n)

[edit:] вы также можете взглянуть на связанный вопрос, который я задавал ранее: Big O, как вы рассчитываете / аппроксимируете его? , который может дать вам подсказку, как вы можете справиться с приближением в целом

Answer 2

Предполагая, что сложение и умножение считаются как одна операция, эта функция выполняет O (m ^ n) операций.

Сначала рассмотрим функцию мульт. Он (mult a b) выполнит ровно a-1 сложения. Поскольку асимптотический рост такой же, давайте для математической простоты приблизим его к a.

Теперь для функции power-of-of, она выполняет n вызовов функции mult. Эти вызовы: (mult 1 m), дают m, затем (mult m m), дают m ^ 2, затем (mult m ^ 2 m), дают m ^ 3 и так далее до m ^ n. Таким образом, общее количество выполненных здесь операций представляет собой сумму m ^ 0 + m ^ 1 + ... + m ^ n. Это (m ^ n - 1) / (m-1), которое растет как m ^ n.