J'aurais besoin d'un petit coup de main concernant les complexités d'algorithmes.. En effet je cherche à déterminer la complexité d'un algorithme contenant 2 boucles for imbriquées.
Et dans un cas plus général existe t'il une formule permettant de déterminer une complexité à n boucles for ?
Je vous mets le code dont je cherche à déterminer la complexité :
public Tableau triMaximum() {
for (int i = 0; i < this.array_int.length; i++) {
int posmaxi = i;
for (int j = i + 1; j < this.array_int.length; j++) {
if (this.array_int[j] > this.array_int[posmaxi]) {
posmaxi = j;
}
}
if (posmaxi != i) {
int maxi = this.array_int[posmaxi];
this.array_int[posmaxi] = this.array_int[i];
this.array_int[i] = maxi;
}
}
return this;
}
Ce tri est le "tri par sélections". La complexité est O(n*n) pour les comparaisons et O(n) pour les échanges (dans ce cas).
C'est la variante la mieux optimisée pour cet algorithme.
Tu peux améliorer en faisant 'i < this.array_int.length - 1'
car tu n'as pas besoin de comparer le dernier élément avec lui-même.
Ce tri est stable et le nombre de comparaisons est le même, peu importe l'ordre initial.
Il sera : n * (n - 1) / 2
Le nombre d'échange varie de 0 (déjà trié) à n-1 (trié en ordre inverse).
La complexité d'une boucle 'for' est O(n) si tous les éléments sont parcourus.
Pour les boucles imbriquées, c'est plus compliqué.
Par exemple, dans l'algorithme de tri par sélections, la boucle extérieure est parcourue n-1 fois.
Mais la boucle intérieure est parcourue de moins en moins de fois, commençant à n-1 et finissant à 1.
En plus dans la complexité d'un algorithme, il faut considérer ce qui demande le plus de ressources.
En général, c'est le temps d'exécution, mais ça peut être la mémoire.
Un autre exemple est un produit matriciel où on a trois boucles imbriquées.
Si je suppose que les matrices sont carrées et de dimension 'n', la complexité sera de l'ordre de O(n*n*n) ou O(n³)
On aura:
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
c[i][j] = 0;
for(int k = 0; k < n; k++) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
Pour des matrices non carrées dont les dimensions sont [m,n] et [n,l], la complexité sera O(m*n*l)
- Edité par PierrotLeFou 8 mars 2020 à 2:36:59
Le Tout est souvent plus grand que la somme de ses parties.
Complexité boucles for imbriquées
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.