Complexité Algorithmique
bidjoss
Messages postés
24
Date d'inscription
Statut
Membre
Dernière intervention
-
Nabla's Messages postés 18203 Date d'inscription Statut Contributeur Dernière intervention -
Nabla's Messages postés 18203 Date d'inscription Statut Contributeur Dernière intervention -
Bonjour,
Je voulais savoir quelle est la complexité de boucles emboitées.
J'en utilise 6 (4 for et 2 if) et je voulais savoir s'il valait mieux chercher une autre solution (les données à traiter sont volumineuses).
Si vous avez un site intéressant sur la complexité, je suis preneur, j'en ai pas trouvé de très clairs...
Merci beaucoup
Je voulais savoir quelle est la complexité de boucles emboitées.
J'en utilise 6 (4 for et 2 if) et je voulais savoir s'il valait mieux chercher une autre solution (les données à traiter sont volumineuses).
Si vous avez un site intéressant sur la complexité, je suis preneur, j'en ai pas trouvé de très clairs...
Merci beaucoup
A voir également:
- Complexité Algorithmique
- Videosurveillance algorithmique - Accueil - Protection
- Besoin d'aide sur la complexité - Forum Algorithmes / Méthodes
- Exercices corrigés en algorithmique pdf première année pdf ✓ - Forum Programmation
- Complexite et np completude - Forum Programmation
- Cours algorithmique - Forum Programmation
9 réponses
Tu veux garder tes secrets?!!
Voila mes boucles (c'est du MATLAB)
for i=(1:size(R,1))
for j1=(1:size(Efin,1))
for j2=(1:size(Efin,2))
if Efin(j1,j2)==R(i,1)
for k=(j2:size(Efin,2))
if Efin(j1,k)==R(i,2)
nbpaires=nbpaires+1;
lEfin(nbpaires,1)=R(i,1);
lEfin(nbpaires,2)=R(i,2);
end
end
end
end
end
end
Voila mes boucles (c'est du MATLAB)
for i=(1:size(R,1))
for j1=(1:size(Efin,1))
for j2=(1:size(Efin,2))
if Efin(j1,j2)==R(i,1)
for k=(j2:size(Efin,2))
if Efin(j1,k)==R(i,2)
nbpaires=nbpaires+1;
lEfin(nbpaires,1)=R(i,1);
lEfin(nbpaires,2)=R(i,2);
end
end
end
end
end
end
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
--ce que je veux dire, c'est que si t'as 2 for, l'un qui fait un balayage sur une taille fixe (for i = 1 à 3), et l'autre de taille variable, alors c'est linéaire
si t'as 2 balayages sur une taille variable (comme ca semble être ton cas) alors c'est une complexité exponentielle
si t'as 2 balayages sur une taille variable (comme ca semble être ton cas) alors c'est une complexité exponentielle
Merci
Je crois avoir compris ton message, j'ai donc l'impression d'être en mode exponentielle à cause de cette ligne
for k=(j2:size(Efin,2))
Je vais voir ce que je peux faire.
Quant au reste, si ce for était en mode de 1 à n, je serais en O(n)?
NablaNablaNabla l'hypnotiseur?!!
Je crois avoir compris ton message, j'ai donc l'impression d'être en mode exponentielle à cause de cette ligne
for k=(j2:size(Efin,2))
Je vais voir ce que je peux faire.
Quant au reste, si ce for était en mode de 1 à n, je serais en O(n)?
NablaNablaNabla l'hypnotiseur?!!
NablaNablaNabla l'hypnotiseur?!!==>pas pigé ....
vois si tu as un moyen de remplacer, mais bien souvent tu n'as pas le choix, surtout avec un faible nombre d'instructions comme tu as là.
des fois, déporter une partie des opérations en dehors de la boucle permet de gagner du temps
exemple (désolé, je parles pas matlab, je parle C/C++)
dans cet exemple, il va par exemple créer 5 fois la variable j, puis lui mettre son contenu
alors que faire ce qui suit marche tout aussi bien:
et la on ne crée qu'une fois la variable....
donc dans cet exemple, tu as une partie temps constant d'execution y=1 qui a remplacé un truc y=x ... je suis aps bon avec les maths mois, ca me croque le cerveau ;)
et si tu avais de boucles for, ca aurai pu donné un truc y=x²...
donc bon, voila, c'est juste pour te dire déviter , si possible, de metrte certaines opérations dans du code: sur un petit exemple ca change pas grand chose, mais sur des gros volumes, tu perds vite du temps inutilement
vois si tu as un moyen de remplacer, mais bien souvent tu n'as pas le choix, surtout avec un faible nombre d'instructions comme tu as là.
des fois, déporter une partie des opérations en dehors de la boucle permet de gagner du temps
exemple (désolé, je parles pas matlab, je parle C/C++)
for(int i = 0; i<5;i++)
{
int j=5 + variable_que_tu_va_lire_ché_pa_ou[i];
cout<<j;
}
dans cet exemple, il va par exemple créer 5 fois la variable j, puis lui mettre son contenu
alors que faire ce qui suit marche tout aussi bien:
int j;
for(int i = 0; i<5;i++)
{
j=5 + variable_que_tu_va_lire_ché_pa_ou[i];
cout<<j;
}
et la on ne crée qu'une fois la variable....
donc dans cet exemple, tu as une partie temps constant d'execution y=1 qui a remplacé un truc y=x ... je suis aps bon avec les maths mois, ca me croque le cerveau ;)
et si tu avais de boucles for, ca aurai pu donné un truc y=x²...
donc bon, voila, c'est juste pour te dire déviter , si possible, de metrte certaines opérations dans du code: sur un petit exemple ca change pas grand chose, mais sur des gros volumes, tu perds vite du temps inutilement
Okay merci Nabla,
Rq : Nabla est un hypnotiseur qui fait des "animations" dans des écoles dont j'ai beaucoup entendu parler.
Rq : Nabla est un hypnotiseur qui fait des "animations" dans des écoles dont j'ai beaucoup entendu parler.
