Complexité Algorithmique Fermé

Question

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

Nabla's · Answer

2 boucles imbriquées, ca peut être exponientiel ! mais des fois, on a pas le choix ...

bidjoss · Answer

Merci de la réponse
Et pour 6 alors?!!!

Comment on détermine si c'est exponentielle?

Nabla's · Answer

ca dépend de la manière dont varie tes boucles for

bidjoss · Answer

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

Nabla's · Answer

--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

bidjoss · Answer

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?!!

Nabla's · Answer

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++)
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

bidjoss · Answer

Okay merci Nabla, 

Rq : Nabla est un hypnotiseur qui fait des "animations" dans des écoles dont j'ai beaucoup entendu parler.

Nabla's · Answer

Nabla est beaucoup de choses:
Nabla est un hypnotiseur
Nabla est un opérateur mathématique (j'ai appris ca que récemment)
Nabla est surtout mon prénom à l'envers ! (c'est un peu pour ca que c'est mon pseudo)

Complexité Algorithmique

9 réponses

Discussions similaires