временная сложность составной функции с точки зрения п

Question

Предполагая, что n является положительным целым числом, составная функция выполняет следующее:

(define (composite? n)
  (define (iter i)
    (cond ((= i n) #f)
          ((= (remainder n i) 0) #t)
          (else (iter (+ i 1)))))
  (iter 2))

Мне кажется, что сложность времени (с жесткой границей) здесь равна O (n) или, скорее, большая тета(п).Я просто смотрю на это прямо сейчас.Поскольку мы добавляем 1 к аргументу iter каждый раз при прохождении цикла, кажется, что это O (n).Есть ли лучшее объяснение?

Answer 1

Как написано, функция O (n).Но если вы измените тест (= in) на (

Answer 2

Разные люди будут давать вам разные ответы в зависимости от того, что они предполагают и что они учитывают в проблеме.

Это O (n), если предположить, что операции равенства и остатка, которые вы выполняете внутри каждого цикла, равны O (1).Это правда, что процессор делает это в O (1), но это работает только для чисел с фиксированной точностью.Поскольку речь идет об асимптотической сложности, а поскольку «асимптотика», по определению, имеет дело с тем, что происходит, когда вещи растут без ограничений, нам необходимо рассмотреть числа, которые являются сколь угодно большими.(Если бы числа в вашей задаче были ограничены, то время выполнения алгоритма также было бы ограничено, и, таким образом, весь алгоритм был бы технически O (1), очевидно, не то, что вы хотите.)

Для произвольного-точные числа, я бы сказал, что равенство и остаток в общем случае требуют времени, пропорционального размеру числа, которое является log n.(Если вы не можете оптимизировать это в амортизированном анализе каким-либо образом) Итак, если мы рассмотрим это, алгоритм будет O (n log n).Кто-то может считать это придирчивым