Discussion :

[souviron34]

C'est simplement parce que la complexité arithmétique n'est pas en O(N). Tu as supposé à tort que le coût du log était identique à celui des autres opérations présentes dans ton algorithme. C'est le calcul initial de ton compte d'opérations qui est faux.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
a = 0
for ( i = 1 ; i < N ; i++ )
   a = a + log(i)

Qu'est-ce qu'il y a de complexe là-dedans ??

On est bien d'accord que la complexité de cette boucle sera O(N), non ??

La partie en O(N²) ne peut pas être une simple addition pour la bonne raison qu'elle doit dépendre de N. De plus, si tu utilises la notation de Landau, c'est que tu raisonnes pour N grand; sinon, tu dois expliciter le compte d'opérations sans négliger aucun terme. Tu ne pas dire que N² est plus grand que 100*N sans supposer que N tend vers l'infini. Tu fais en plus une erreur de raisonnement ici qui ne remet pas du tout en cause la valeur asymptotique d'un calcul de complexité.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
for ( i = 0 ; i < N ; i++ )
   for ( j = 0 ; j < N ; j++ )
     {
         if ( i != j )
            x[i] = x[i] + tab[j]
     }
 
for ( num = 0 ; num < 10 ; num++ )
   for ( i = 0 ; i < N ; i++ )
       tab[i] =  x[i]^10 + log(x[i])*4 + exp(x[i])/x[i] + ......

On est bien d'accord que les constantes ne comptent pas, donc la deuxième boucle a une complexité en O(N), non ??.....

Et pourtant l'algo est censé avoir une complexité en O(N^2) à cause de la première...

[kwariz]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
a = 0
for ( i = 1 ; i < N ; i++ )
   a = a + log(i)

Qu'est-ce qu'il y a de complexe là-dedans ??

On est bien d'accord que la complexité de cette boucle sera O(N), non ??

Cette boucle fait N assignations de a, N assignations de i, N incrémentations, N comparaisons, N-1 additions et N-1 calcul de log.

C(N)=N(2Cass + Ccomp+Cinc) + (N-1)(Cadd+Clog)
En supposant que Cass, Ccomp, Cinc, Cadd, Clog sont des constantes alors C(N)=6N-2
donc C(N) est en O(N).
Si Clog dépend du nombre de bit de son argument : Clog<(log N)^2
C(N)<5N-1+ (N-1)(logN)^2
C(N) sera en O(N (logN)^2)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
for ( i = 0 ; i < N ; i++ )
   for ( j = 0 ; j < N ; j++ )
     {
         if ( i != j )
            x[i] = x[i] + tab[j]
     }
 
for ( num = 0 ; num < 10 ; num++ )
   for ( i = 0 ; i < N ; i++ )
       tab[i] =  x[i]^10 + log(x[i])*4 + exp(x[i])/x[i] + ......

On est bien d'accord que les constantes ne comptent pas, donc la deuxième boucle a une complexité en O(N), non ??.....

Et pourtant l'algo est censé avoir une complexité en O(N^2) à cause de la première...

Les mêmes calculs peuvent être faits sur ces 2 boucles en gros l'algo sera toujours en O(N^2).

[Aleph69]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
a = 0
for ( i = 1 ; i < N ; i++ )
   a = a + log(i)

Qu'est-ce qu'il y a de complexe là-dedans ??

On est bien d'accord que la complexité de cette boucle sera O(N), non ??

Compte d'opérations grossier :
N sommes
N logarithmes
et le reste (opérations dans les boucles et affectations)

Soient S le coût de + et L le coût de log, on a : (S+L)*N.
Si S=L, alors on a 2*S*N.
Sinon, on peut toujours majoré le compte par 2*max{S,L}*N.

Dans chaque cas, tu as un comportement en O(N) mais la constante diffère. Si le coût de L correspond à M opérations et S à 1 opérations, on trouve dans le premier cas
(M+1)*N
et dans le dernier cas
2*M*N
Bref, tout dépend de tes hypothèses de calcul.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
for ( i = 0 ; i < N ; i++ )
   for ( j = 0 ; j < N ; j++ )
     {
         if ( i != j )
            x[i] = x[i] + tab[j]
     }
 
for ( num = 0 ; num < 10 ; num++ )
   for ( i = 0 ; i < N ; i++ )
       tab[i] =  x[i]^10 + log(x[i])*4 + exp(x[i])/x[i] + ......

Je te laisse faire les comptes d'opérations à titre d'exercice et après on en discute si tu veux.

[souviron34]

D'après ce que je comprend, prendre en compte les opérations faites pour une itération se calcule avec la complexité cyclomatique.

La complexité algorithmique standard d'un algorithme se base est une mesure de l'influence d'un paramètre d'entrée... quelque soit le nombre d'opérations dedans.

Une boucle simple donnera une compleité en O(N), une double en O(NM).

C'est bien pour ça que, par rapport au post initial et aux diverses réponses, il y a une certaine ambiguité, et que d'une part il y a différentes notions de complexité, et d'autre part aucune n'est vraiment "sûre"..

Chacune mesure quelque chose à sa façon.

La plus utile parce qu'elle est "prédictive" est la complexité algorithmique, car elle permet de prédire le comportement temporel en fonction du nombre d'entrées (si je double l'entrée, je multiplie le temps par...), quel que soit le nombre d'opérations et la manière dont c'est implanté.

Maintenant, la complexité cyclomatique est possible à analyser pour un algo simple, très nettement, voire quasi impossible, pour un algo très complexe. Elle donnera aussi une indication, mais très nettement moins prédictive, car elle dépendra du processeur et de ses opérations cablées, des optimisations, etc..


Disons que pour répondre au post initial et à ses diverses interprétations, je pense que la réponse indiquée par moi dans la discussion parallèlle ici ainsi que le lien donné par Franck dans le post plus bas sont des bonnes lignes pour s'y retrouver..

Enfin, il me semble...

Visblement (et ça se voit dans les liess Wiki), les définitions sont complexes à appréhender et à mettre en pratique pour es esprits non spécialement formés...

[kwariz]

D'après ce que je comprend, prendre en compte les opérations faites pour une itération se calcule avec la complexité cyclomatique.

Non, quand on détermine la complexité algorithmique il faut prendre en compte ce qui est fait dans une boucle, toujours.

La complexité algorithmique standard d'un algorithme se base est une mesure de l'influence d'un paramètre d'entrée... quelque soit le nombre d'opérations dedans.

Une boucle simple donnera une compleité en O(N), une double en O(NM).

Cela dépend de ce qui est fait dans la boucle. Si le corps de la boucle est d'une complexité en O(f(n)) alors la boucle aura une complexité en O(Nf(k)), ici k peut dépendre de N évidemment.

C'est bien pour ça que, par rapport au post initial et aux diverses réponses, il y a une certaine ambiguité, et que d'une part il y a différentes notions de complexité, et d'autre part aucune n'est vraiment "sûre"..

Chacune mesure quelque chose à sa façon.

Parler de complexité est généralement non ambigu dans un contexte. Mais il est vrai que les confusions sont faciles. Quand on dit que quicksort est en O(n lg n) il faudrait préciser que ce qui est mesuré est le nombre de comparaisons et que n est la taille du tableau passé en entrée. Alors que dire que bucketsort est O(n+k) ne donne absolument pas la même mesure, pourtant ils'agit du même "n", dans les deux cas il s'agit d'algo de tris, ...
Il faudrait en outre préciser quel modèle de calcul est utilisé (généralement une machine de Turing ou une machine RAM, parfois une modèle quantique).
Bref comme dans tous les domaines mathématiques il faut être rigoureux et précis (enfin souvent).