Re: séquence des voyelles

par **manianis** le Sam 8 Déc - 20:36

Admin a écrit:C'est à peu près comme la recherche du plus grand élément dans un tableau: il faut parcourir tout le tableau. C'est en O(n) la complexité.

NB: O(n) ne veut pas dire "n"

çà veut dire que la complexité du problème est proportielle à la valeur de n.

par **nabiL** le Sam 8 Déc - 20:46

Pas forcément Proportonnelle à n, car sinon: O(n²) veut dire Proportionnelle à n²: ce qui est faux.
O(n^k) => Complexité polynomiale de degré k.

par **manianis** le Sam 8 Déc - 22:02

Code:: Pour i=1 to n Faire Pour j=1 to m Faire traitement Fin Pour Fin Pour

Quelle est la complexité de cette portion d'algorithme ?

par **nabiL** le Sam 8 Déc - 22:17

Elle est polynomiale. Elle vaut nxm opérations Traitements.
Soit N = max(m,n), alors, elle est en O(N²) (en réalité O(m,n)).
Le nombre d'affectation lors de l'initialisation d'une matrice A(m,n) est mxn.