временная сложность функции acc в схеме?

Question

Я пытался найти сложную временную сложность для этой функции в отношении только одного из аргументов.Я думал, что это O (p ^ 2) (или, скорее, большая тета), но я больше не уверен.

(define (acc p n)
  (define (iter p n result)
    (if (< p 1) 
        result
        (iter (/ p 2) (- n 1) (+ result n))))
  (iter p n 1))

Answer 1

@ sarahamedani, почему это будет O (p ^ 2)?Это выглядит как O (log p) для меня.Время выполнения должно быть нечувствительным к значению n.

. Вы суммируете последовательность чисел с обратным отсчетом от n.Количество повторений iter зависит от того, сколько раз p можно уменьшить вдвое, не став меньше 1. Другими словами, позиция крайнего левого бита '1' в p, минус один, является числомраз iter будет повторяться.Это означает, что число iter прогонов пропорционально log p.

Answer 2

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

На данный момент мы можем принять очень простую модель машины, в которой арифметические операции и поиск переменных имеют постоянное время.

Пусть iter-cost будет именем функции, которая подсчитывает, сколько шагов требуется для вычисления iter, и пусть это будет функция p, поскольку завершение iter зависит только от p , Тогда вы сможете писать выражения для iter-cost(0). Вы можете сделать это для iter-cost(1), iter-cost(2), iter-cost(3) и iter-cost(4)?

В целом, если p больше нуля, можете ли вы выразить iter-cost(p)? Это будет в терминах констант и повторного вызова iter-cost. Если вы можете выразить это как повторение, тогда вам будет легче выразить это в закрытом виде.