Discussion :

[jp.lorient]

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

par exemple en exercice :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[icsor]

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) .

[jp.lorient]

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 ...
sinon effectivement si on test avec i c'est bien O(1)

[icsor]

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é)

[rours]

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

complexité (environt) = m/n.