Quelle est la complexité temporelle de cette fonction d'exponentiation de schéma?

Question

Quelle est la complexité du temps? Pourquoi?

(define (mult a b) 
     (define (internal a accum) 
     (if (= a 1) accum 
      (internal (- a 1) (+ accum b)))) 
     (internal a b)) 

(define (to-the-power-of m n) 
    (define (internal x accum) 
    (if (= x 0) accum 
     (internal (- x 1) (mult accum m)))) 
    (internal n 1)) 

Answer 1

addition et multiplication En supposant que les deux sont comptés comme une seule opération, cette fonction exécute des opérations O (m^n).

Considérons d'abord la fonction mult. Il (mult a b) effectuera exactement un-1 additions. Puisque, la croissance asymptotique est la même, approximons cela par a, pour la simplicité mathématique. Désormais, pour la fonction to-the-power-of, elle effectue n appels à la fonction mult. Ces appels sont à (mult 1 m), donnent m, puis à (mult m m), ce qui donne m^2, puis à (mult m^2 m), ce qui donne m^3 et ainsi de suite jusqu'à m^n. Donc le nombre total d'opérations effectuées ici est la somme m^0 + m^1 + ... + m^n. C'est (m^n - 1)/(m-1) qui grandit comme m^n.

Answer 2

la complexité de temps pour la partie mult se trouve comme ceci:

pour calculer (mult ab), (un accum interne) est appelée jusqu'à ce qu'un = 1 donc nous avons une sorte de récursion de queue (boucle) qui itère sur a.

nous savons donc que la complexité temporelle de (mult ab) est O (a) (= complexité temporelle linéaire)

(à la mise sous tension de mn) dispose également d'un (interne x accum) définition, qui boucle également (jusqu'à x = 0)

donc à nouveau, nous avons O (x) (= complexité temporelle linéaire)

Mais: on n'a pas pris en compte le temps nécessaire pour les appels de fonction de l'interne ...
En interne, nous utilisons la définition (mult ab) qui est linéaire dans la complexité temporelle donc nous avons le cas suivant: dans la première itération mult est appelée avec: (mult 1 m) -> O (1)
deuxième itération cela devient: (mult mm) -> O (m)
troisième itération: (mult m² m) -> O (m * m) et ainsi de suite Il est clair que cela se développe jusqu'à n = 0 (ou en interne cela devient x = 0)

donc on peut dire que la complexité du temps dépendra m et n: O (m^n)

[modifier :] vous pouvez également jeter un oeil à une question connexe que j'ai posée plus tôt: Big O, how do you calculate/approximate it? qui peut vous donner une idée de comment vous pouvez gérer l'approximation plus généralement