Calcul de Complexité

Bonjour à tous,
Ayant un partiel lundi prochain j'ai quelques questions sur le calcul de complexité

par exemple en exercice :

Code:

---

1 2 3 4 5 6 7 8 9

Algorithme F(n:entier,m:entier) i=0; si (i>0) alors { tant que (m>=n) faire { m=m-n; i++; } return i }

---

on demande ce que calcule cet algo j'ai répondu qu'il calculait la division de m en partie entière plus le reste : i * n + derniere_valeur_de_m = m
On demande le nombre maximum d'itération en fonction de n et m
j'ai répondu qu'on faisait au maximum m+1 itération mais pour n je ne sais pas.
et la complexité de la fonction en fonction de n et m ?

Merci pour vos futures réponses

Bonjour,

votre problème est fort simple.

Votre programme déclare la variable i = 0. Votre programme ne fait quelque chose avec m et n que si cette variable i est strictement positive. Donc votre programme renvoie tout simplement 0, et a comme complexité O(1) ;) .

Bonjour icsor et merci de votre réponse
Je me suis rendu compte que j'avais mal tapé l'énoncé
dans la condition c'est si (n>0) alors ... :oops:
sinon effectivement si on test avec i c'est bien O(1)

Bonjour,

sans l'erreur, votre algorithme fait bien une division et renvoie bien le résultat de la division.

Pour le nombre d'itération, il dépend de m et de n. Essayer avec des exemples en prenant n = 2, puis n = 3 pour voir combien d'itérations vous avez. (et une fois que vous aurez le nombre d'itération, vous aurez la complexité)

au mieu : 0 passage dans la boucle.
Au pire : m passage, quand n = 1

complexité (environt) = m/n.