salut tous,

je voudrais savoir comment calculer la complexité d'algorithmes, je comprends que c'est lié au nombre d'opérations (et donc au nombre de boucles) mais je n'ai pas trop compris comment faire pour calculer ceci rigoureusement....

pourriez vous me donner deux exemples s'il vous plait ?

1°) pour le calcul d'un déterminant
2°) pour la résolution d'un systeme lineaire triangulaire inférieur (ca doit etre pareil pour le superieur)

merci d'avance pour votre aide

Il y a une section des tutos du SdZ Informatique dédié à l'algorithmique. On y trouve notamment ce cours qui introduit la notion de complexité. J'espère que tu y trouveras ton bonheur.

merci de ta reponse
en fait je cherchais une explication un peu plus mathematique... (où j'ai pas regardé au bon endroit...)

L'explication ne change pas vraiment. On compte simplement le nombre d'opérations que l'on effectue pour faire le calcul, en fonction des paramètres pertinents.

Par exemple, calculer un déterminant avec la formule naïve de définition, pour une matrice de taille <math>\(n\)</math> quelconque, ça demande a priori d'effectuer <math>\(n!\)</math> additions de termes calculés par <math>\(n\)</math> multiplications.
On connaît donc le nombre d'additions (<math>\(n!\)</math>) et de multiplications (<math>\(n \times n!\)</math>) nécessaires, après tout dépend de ce qui nous intéresse comme opération (si on les prend toutes, si on veut que les multiplications, en considérant qu'une addition ça coûte beaucoup moins cher...).

Et quand on arrive à des nombres assez grands, on vient à s'intéresser surtout à l'ordre de grandeur du nombre d'opértions : ici, on doit effectuer <math>\(\mathcal O((n+1)!)\)</math> (c'est-à-dire quelque chose qui est (a peu près) proportionnel à <math>\((n+1)!\)</math>).

merci pour cette réponse, c'est ce genre de reponse que je cherchais.

=> pour le calcul du determinant peux tu me detailler vite fait fait stp comment tu tombe sur (n+1)! j'ai pas trop compris.

=> par exemple si j'ai un algo qui ressemble à ceci:

for i=1:n
somme=somme+1;
for j=i+1:k
multi=multi*n
end
end

comment puis je déterminer la complexité ? j'aimerai comprendre avec une explication similaire avec ce que tu m'as donné...

merci d'avance

Dans ton exemple, ne considérons que le nombre de multiplications (car comme Locke le disait, une addition est beaucoup moins coûteuse).
Si tu prends la boucle sur j : tu fais une multiplication pour chaque j, et il y a k-(i+1)+1 = k-i passages, soit (k-i)*1 = k-i multiplications.
Maintenant, prenons la boucle sur i : on sait maintenant que pour chaque i, tu vas faire k-i multiplications.
Or i va de 1 à n, donc tu vas effectuer (k-1)+(k-2)+...+(k-n) multiplications, soit <math>\(nk-(1+2+...n) = nk-\dfrac{n(n+1)}{2}\)</math>

Bon, ça, c'est le nombre exact de multiplications que tu vas faire. Souvent, on ne s'intéresse qu'à l'ordre de grandeur. Tu as quoi comme info sur la valeur de k? Est-ce qu'elle dépend de n? Est-ce que c'est une constante (mais ça serait bizarre, vu qu'il faut que n soit plus petite que k)?

merci pour cette réponse c'est super !!!

deux solutions possibles
=> "k" est quelconque
=> "k" est egale à "n+1"