Complexité du temps entier dans Haskell

Question

J'ai eu une mission à l'école la semaine dernière pour mettre en œuvre une fonction de calcul du nième nombre dans la séquence de fibonacci. Une 'sous-affectation' devait l'implémenter en utilisant l'accumulation (peut-être pas une traduction correcte) afin de donner à la fonction O (n) une complexité temporelle. Tout a bien fonctionné jusqu'à ce que j'essaie de faire la fonction (Int -> Integer). En expérimentant un peu, j'ai réalisé que la complexité temporelle était proche de O (n^2) pour les nombres vraiment grands. Il me semble que cela doit être dû à l'implémentation d'Integer, ce qui me rend un peu curieux de savoir comment cela fonctionne. J'ai fait quelques recherches sur Google et je n'ai rien trouvé qui me paraissait utile, alors je me tourne vers vous dans l'espoir d'obtenir une explication ou un lien qui l'explique à fond.

Mon code:

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" 

Je suis reconnaissant pour toutes les réponses

Viktor

Answer 1

Cela n'a rien à voir avec Haskell vraiment, il est juste en raison du fait que les nombres de Fibonacci grandir exponentiellement rapidement. Spécifiquement, le nième nombre de Fibonacci a environ (log φ) n ou environ 0,48 n bits où φ est le nombre d'or (1 + sqrt 5)/2. Puisque l'addition d'entiers de k bits prend le temps O (k), vos additions O (n) prennent en fait un total de O (n^2) temps, car en moyenne les nombres que vous ajoutez ont O (n) bits.

(Note pour sticklers:. Grande O devrait vraiment être grand Theta dans le ci-dessus)

Answer 2

Pour ajouter à Reid's answer, le fait que votre algorithme a O (N) la complexité du temps dépend de ce que vous considérez être le étape d'exécution. C'est une idée fausse commune de la complexité temporelle: cette complexité temporelle correspond toujours au temps d'exécution. Ce qui doit être pris en compte dépend de la profondeur à laquelle nous voulons analyser le problème. Si vous définissez une étape comme une addition de Integer, oui, votre algorithme avec des accumulateurs s'exécute en temps O (N). Si vous définissez une étape comme une addition de mots (une addition de 32 ou 64 bits), elle s'exécute dans O (N^2) comme Reid l'a expliqué. Si vous voulez que votre analyse de complexité corresponde au temps d'exécution, vous devez utiliser une étape d'exécution dont le temps d'exécution est délimité ci-dessus par une constante, comme l'ajout de deux mots de processeur. L'ajout d'entiers ne l'est pas, car les entiers peuvent être arbitrairement grands.