Целочисленная сложность времени в Хаскеле

Question

У меня было задание в школе на прошлой неделе, чтобы реализовать функцию для вычисления n: th числа в последовательности Фибоначчи. «Подзадача» заключалась в том, чтобы реализовать ее с использованием накопления (возможно, это не правильный перевод), чтобы дать функции O (n) временную сложность. Это все работало нормально, пока я не попытался сделать функцию (Int -> Integer). Немного поэкспериментировав, я понял, что сложность по времени была близка к O (n ^ 2) для действительно больших чисел. Мне приходит в голову, что это должно быть из-за реализации Integer, которая заставляет меня немного любопытно о том, как это работает. Я сделал несколько поисков в Google и не нашел ничего полезного, поэтому обращаюсь к вам, ребята, в надежде получить объяснение или ссылку, которая объясняет это полностью.

Мой код:

ackfib 0 = 0
ackfib 1 = 1        
ackfib n = loop n 1 0 1
    where
        loop n n1 n2 i 
            | i < n     = loop n (n1+n2) n1 (i+1)
            | i == n    = n1
            | i > n     = error "n must be greater than or equal to 0"

Я благодарен за все ответы

Виктор

Answer 1

Это на самом деле не имеет ничего общего с Хаскеллом, это просто результат того факта, что числа Фибоначчи быстро растут в геометрической прогрессии. В частности, n-е число Фибоначчи имеет около (log ₂ ) n или примерно 0,48 n бит, где & phi; это золотое сечение (1 + sqrt 5) / 2. Так как добавление k-битных целых чисел занимает O (k) время, ваши добавления O (n) фактически занимают всего O (n ^ 2) времени, потому что в среднем числа, которые вы добавляете, имеют O (n) бит.

(Примечание для приверженцев: большой O в действительности должен быть большой тэтой.)

Answer 2

Чтобы добавить к ответ Рейда , тот факт, что ваш алгоритм имеет O (N) сложность времени, зависит от того, что вы считаете шагом выполнения.Это распространенное заблуждение о временной сложности: эта временная сложность всегда соответствует времени выполнения.

То, что нужно рассмотреть на этапе, зависит от того, насколько глубоко мы хотим проанализировать проблему.Если вы определяете шаг как одно добавление Integer, то ваш алгоритм с аккумуляторами выполняется за O (N) времени.Если вы определяете шаг как сложение одним словом (32- или 64-битное сложение), он выполняется в O (N ^ 2), как объяснил Рейд.

Если вы хотите, чтобы анализ сложности соответствовал выполнениювремя вам нужно использовать шаг выполнения, время выполнения которого ограничено сверху константой, например, добавление двух процессорных слов.Добавление целых чисел - нет, поскольку целые числа могут быть сколь угодно большими.