Какова временная сложность этой функции возведения в степень схемы?
Какая временная сложность? Почему?
(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))
Следите за своим стилем отступа? Можно подумать, что функция to-the-power-of является частью функции mult.
Ответы 2
Предполагая, что сложение и умножение считаются одной операцией, эта функция выполняет O (m ^ n) операций.
Сначала рассмотрим функцию mult. Он (mult a b) выполнит ровно a-1 сложений. Поскольку асимптотический рост такой же, давайте аппроксимируем его a для математической простоты.
Теперь, что касается функции, она выполняет n вызовов функции mult. Эти вызовы: (mult 1 m), yield 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.
временную сложность для части mult можно найти так:
для вычисления (mult a b), (внутренний a аккумулятор) вызывается до тех пор, пока a = 1 так что у нас есть своего рода хвостовая рекурсия (цикл), которая выполняет итерацию по a.
Таким образом, мы знаем, что временная сложность (mult a b) равна О (а) (= линейная временная сложность)
(to-the-power-of m n) также имеет определение (внутреннее накопление x), которое также зацикливается (до x = 0)
так что снова у нас есть О (х) (= линейная временная сложность)
Но: мы не учли время на вызовы функций внутренних ...
Во внутреннем мы используем определение (mult a b), которое линейно по временной сложности, поэтому мы имеем следующий случай:
в первой итерации mult вызывается с помощью: (mult 1 m) -> O (1)
во второй итерации это становится: (mult m m) -> O (m)
третья итерация: (мульт м² м) -> O (м * м)
и так далее
Понятно, что это растет до n = 0 (или во внутреннем становится x = 0)
таким образом, мы можем сказать, что временная сложность будет зависеть от m и n: О (м ^ п)
[edit:] вы также можете взглянуть на связанный с этим вопрос, который я задал ранее: Большой О, как вы его рассчитываете / приближаете?, который может дать вам ключ к пониманию того, как вы можете обрабатывать приближение в более общем плане
Выглядят они знакомо - я писал это для вас примерно неделю назад?