Discussion :

[sara162794]

Salut
J'envisage de déterminer la complexité de l'algorithme suivant

Code :

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

1
2
3
4
5
6
7
8
9
10
11
function2 (entier n,entier m):entier
var résultat: entier 
Début
résultat=0
 pour i de 1 à n faire
    pour j de 1 à m faire 
       résultat =résultat+i*j
    Finpour
 Finpour
return résultat
Fin

Puisque je suis débutante et je ne maitrise pas encore les ce genre de calcul je pose C1(n) la complexité de la boucle pour i, C2(m) celle de la boucle pour j..

ainsi C1(n)=C2(m)*n(n+1)/2 et C2=O(1)*m(m+1)/2 et là je me bloque et je ne sais même pas si ce calcul est correct...

Qlq peut m'aider et merci d'avance

[picodev]

Bonjour,
Lorsqu'on parle de complexité on parle classiquement de complexité en temps ou aussi de complexité en espace. Ici je suppose que tu parle d'une complexité en temps. Il y a aussi les notions de complexité dans le «pire cas», «en moyenne», … et les notions de O (grand oh), Ω (grand oméga), Θ (grand thêta)…
Ici ton algorithme est relativement simple. On commence par l'intérieur de la boucle. La ligne 7 contient 3 lectures en mémoire, une multiplication, une addition et une écriture mémoire. Nous allons considérer ces opérations en temps constant → O(1).
Cette ligne est exécutée m fois (la boucle j) les opérations de boucles (incrémentation du compteur, …) sont considérées en temps constant ici. Donc les lignes 6-8 ont une complexité de m*O(1)+O(1) ∈ O(m).
De la même manière cette boucle est exécuté n fois par une autre boucle. Les lignes 5-9 auront une complexité en temps de O(mn). Les autres lignes de l'algorithmes seront effectuées en temps constant : l'algorithme est donc en O(mn).