Я пытаюсь найти сложную временную сложность для этой функции только по одному из аргументов. Я думал, что это O (p^2) (или, скорее, большая тета), но я не уверен.временная сложность функции acc в схеме?
(define (acc p n)
(define (iter p n result)
(if (< p 1)
result
(iter (/ p 2) (- n 1) (+ result n))))
(iter p n 1))
@sarahamedani, почему это должно быть O (p^2)? Это похоже на O (log p) для меня. Время выполнения должно быть нечувствительным к значению n.
Вы суммируете ряд цифр, считая с n. Количество повторений iter будет зависеть от того, сколько раз p можно уменьшить вдвое, не становясь меньше 1. Другими словами, положение самого левого «1» бита в p, минус одно, - это количество раз, которое iter будет итерировать. Это означает, что количество раз iter прогонов пропорционально log p.
Вы можете попытаться его увидеть или перейти от него более систематически. Предполагая, что мы делаем это с нуля, мы должны попытаться построить отношение повторения от определения функции.
Мы можем считать на данный момент очень простой машинной моделью, где арифметические операции и переменные поисковые запросы являются постоянным временем.
Пусть iter-cost быть имя функции, которая подсчитывает, сколько шагов требуется, чтобы вычислить iter, и пусть это будет функция p, так как iter «s окончание зависит только от p. Затем вы должны иметь возможность писать выражения для iter-cost(0). Можете ли вы сделать это для iter-cost(1), iter-cost(2), iter-cost(3) и iter-cost(4)?
В целом, учитывая p больше нуля, можете ли вы выразить iter-cost(p)? Он будет в терминах констант и повторного вызова iter-cost. Если вы можете выразить это как повторение, то вы можете лучше выразить это в закрытой форме.
Просто, чтобы быть педантичным, он находится в наборе программ O (p^2), говоря исключительно из технического определения. Дело в том, что оно также относится к гораздо меньшему множеству, и мы пытаемся убедить OP, что O (p^2) является способом, слишком свободным от верхней границы. – dyoo