Complejidad del tiempo entero en Haskell

Question

Tuve una tarea en la escuela la semana pasada para implementar una función para calcular el n-ésimo número en la secuencia de fibonacci. Una 'subasignación' consistía en implementarla usando la acumulación (podría no ser una traducción correcta) para dar a la función O (n) complejidad de tiempo. Todo funcionó bien hasta que intenté hacer la función (Int -> Entero). Experimentando un poco me di cuenta de que la complejidad del tiempo estaba cerca de O (n^2) para números realmente grandes. Se me ocurre que esto debe ser debido a la implementación de entero, lo que me hace un poco curioso sobre cómo funciona. Hice algunas búsquedas en Google y no encontré nada que pareciera útil, así que me dirijo a ustedes con la esperanza de obtener una explicación o un enlace que lo explique a fondo.

Mi código:

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" 

Estoy agradecido por todas las respuestas

Viktor

Answer 1

Esto no tiene nada que ver con Haskell en realidad, es sólo una consecuencia del hecho de que los números de Fibonacci crecen exponencialmente rápido. Específicamente, el n. ° número de Fibonacci tiene aproximadamente (log φ) n o aproximadamente 0,48 n bits donde φ es la proporción áurea (1 + sqrt 5)/2. Dado que la suma de enteros de k bits toma O (k) tiempo, sus O (n) adiciones realmente toman un total de O (n^2) tiempo, porque en promedio los números que está agregando tienen O (n) bits.

(Nota para sticklers:. O grande realmente debe ser grande Theta en el anterior)

Answer 2

Para añadir a Reid's answer, el hecho de que el algoritmo tiene O (N) complejidad del tiempo depende de lo que se considera ser el paso de ejecución. Esta es una idea equivocada común de la complejidad del tiempo: la complejidad del tiempo siempre corresponde al tiempo de ejecución.

Qué considerar el paso depende de qué tan profundo queramos analizar el problema. Si define un paso como una adición de Entero, sí, su algoritmo con acumuladores se ejecuta en O (N) tiempo. Si define un paso como una adición de una palabra (una adición de 32 o 64 bits), se ejecuta en O (N^2) como lo explicó Reid.

Si desea que su análisis de complejidad se corresponda con el tiempo de ejecución, necesita usar un paso de ejecución cuyo tiempo de ejecución está delimitado anteriormente por una constante, como la adición de dos palabras de procesador. La adición de enteros no lo es, porque los enteros pueden ser arbitrariamente grandes.