Complexité d'un algorithme

[juliana1]

calculer la complexité de tri par fusion dans le cas ou n=2^p
la meme chose pour le
tri par bulles et tri rapide et tri par insertion

et merci

[ampholyte]

Bonjour,

As-tu écrit tes algorithmes et calculer le nombre d'opération que l'algorithme effectue ?

[juliana1]

Bonjour,

As-tu écrit tes algorithmes et calculer le nombre d'opération que l'algorithme effectue ?

oui

voila pour le tri par bulles :
//tri par bulles
void tri_bulles(int t[30],int n){
int i,j;
int aide;
for(i=0;ii;j--){
if (t[j] > t[j-1]){
aide=t[j-1];
t[j-1]=t[j];
t[j]=aide;
}
}
}
for(i=0;i=p;i--){
t[i]=t[i-1];
}
t[p-1]=x;
for(i=0;i0 ; i--)
{
for (j=0; jt[j+1])
{
aide=t[j];
t[j]=t[j+1];
t[j+1]=aide;
}
}
for(j=0;jt[max])
max=j;
if(max!=i){
aide=t[i];
t[i]=t[max];
t[max]=aide;
}
}
for(i=0;i<n;i++)
printf("%d\t",t[i]);
}

[ampholyte]

Lorsque tu montres du code utilise les balises CODE se sera plus lisible.

Pour chaque algorithme combien d'opération effectues-tu ?

[juliana1]

pour n=2^p

[juliana1]

Lorsque tu montres du code utilise les balises CODE se sera plus lisible.

Pour chaque algorithme combien d'opération effectues-tu ?

oui désolé
j'utilise pour n=2^p

[juliana1]

aucune réponse?

[ampholyte]

Essaye de chercher un peu par toi même en comptant le nombre d'opération qui est effectué. Exemple :

Code: Tout sélectionner

int factorielle = 1;

for (int i = 2; i <= n; i++) {
    factorielle *= i;
}


Ici on a n - 1 itérations où il y a un nombre d'opération élémentaire constant.
On va donc avoir une complexité de O(n)

Exemple 2 :

Code: Tout sélectionner

int somme = 0

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        somme += tab[i][j];
    }
}


Ici on a n*m itérations avec un nombre opération élémentaire constant (1 ici). On va donc avoir une complexité de O(n*m)

As-toi d'essayer d'appliquer ceci à tes exemples