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

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

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

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

Теперь для функции-функции-функции это выполняет 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.

Answer 2

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

для расчета (мульт AB), (внутренний Accum) называется до а = 1 поэтому у нас нет какого-то хвост рекурсии (петля), который итерации над.

мы, таким образом, известны, что временная сложность (мульт AB) является О (а) (= линейная сложности времени)

(к-власти-Мп) также имеет (внутреннюю й Accum) определение, что и петли (до х = 0)

так мы снова O (х) (= линейная сложность времени)

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

, таким образом, можно сказать, что временная сложность будет зависеть от т и п: о (т^п)

[править :] вы также можете взглянуть на связанный с этим вопрос, который я задал ранее: Big O, how do you calculate/approximate it?, который может дать вам представление о том, как вы можете справиться с приближением в целом