Analyse du code de schéma pour l'espace et le temps

Question

Je travaille sur les cours en ligne du MIT pour le cours classique 6.001: La structure et l'interprétation des programmes informatiques. J'essaie d'acquérir une compréhension de l'analyse de la complexité du code en termes d'utilisation de la mémoire par rapport au temps d'exécution. Dans les premières conférences, ils présentent une solution dans Scheme pour la série Fibonacci.

La solution qu'ils présentent dans les vidéos est celle qui a la caractéristique de croître dans l'espace mémoire avec x (performance de la Recursion linéaire), ce qui présente un gros problème avec la série Fibonacci. Comme vous essayez de trouver un plus grand nombre de Fibonacci, l'espace requis pour la récursivité devient énorme. Ils suggèrent d'essayer de trouver un moyen d'obtenir des performances d'itération linéaire, où l'espace mémoire nécessaire reste constant tout au long du calcul et ne dépend pas de x.

Ma solution est ci-dessous. Ma question spécifique est, quelle est l'analyse de performance de mon code Scheme ci-dessous, en termes d'utilisation de la mémoire par rapport au temps d'exécution?

(define (fib x) 

    (define (fib-helper target total current-index i-2 i-1) 
    (if (> current-index target) 
      (if (= target 1) 
       0 
       total) 
      (fib-helper target 
         (+ i-2 i-1) 
         (+ current-index 1) 
         i-1 
         (+ i-2 i-1)))) 

    (fib-helper x 1 3 0 1)) 

Answer 1

Eh bien, étant donné que (fib n) cause n-1 appels à fib-helper, votre solution fonctionne en temps linéaire. fib-helper ne s'appelle qu'une seule fois pour chaque itération, et chaque itération est un appel de queue, de sorte que votre programme s'exécute dans un espace constant.

Cela signifie qu'un appel à (fib 1000) ne devrait prendre que dix fois le temps CPU de (fib 100) tout en prenant la même quantité de mémoire.

Answer 2

En voyant votre appel à fib-helper est un appel de la queue correcte, cela fonctionne dans l'espace constant.

Je ne peux pas vous aider avec le temps d'exécution si :)