Discussion :

[Cocoffx]

Bonsoir à tous,

J'ai du mal à comprendre comment calculer la complexité d'un algorithme, pourriez vous m'aider à comprendre en prenant les deux exemples suivants :


Ex 1 :

Code :

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

1
2
3
4
5
6
7
8
9
input : n,m : entiers positifs
output : nm
s <- m
r <- 0
 
While s >= 1
    r <- r+n
    s <- s-1
return r

Ex 2 :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
input n,m : entiers positifs
output : nm
 
s <- n
k <- m
r <- 0
 
While s > 0
  if s%2 == 1
   r <- r+k
   s <- s/2
   k <- k*2
 return r

[Acrim]

Calculer la complexité signifie calculer le nombre d'opérations nécessaires (en fonction des paramétrés d'entrée) pour exécuter l'algorithme.
Dans l'exemple 1 : on réalise m fois la boucle "while" qui comporte 2 opérations.
Ainsi :
ligne 3 : 1 opération
ligne 4 : 1 opération
ligne 7 : 1 opération
ligne 8 : 1 opération

D'où : 2 + 2 * m opérations
Soit O(m) opérations...

[Cocoffx]

Je ne crois pas, le corrigé m'indique qu'elle est de : O(m log(mn))

Merci quand même ..

[Cocoffx]

En fait de ce que j'ai compris, il faut prendre en compte le nombre d'itérations du while mais aussi la valeur max prise par la variable retournée ..

[ToTo13]

Calculer la complexité signifie calculer le nombre d'opérations nécessaires (en fonction des paramétrés d'entrée) pour exécuter l'algorithme.
Dans l'exemple 1 : on réalise m fois la boucle "while" qui comporte 2 opérations.
Ainsi :
ligne 3 : 1 opération
ligne 4 : 1 opération
ligne 7 : 1 opération
ligne 8 : 1 opération

D'où : 2 + 2 * m opérations
Soit O(m) opérations...

+1

Je ne crois pas, le corrigé m'indique qu'elle est de : O(m log(mn))

Il suffit de le faire à la main pour comprendre, cet algo fait juste n*m
La boucle s'effectue m fois et il y a une simple addition à l'intérieur, addition qui n'affecte pas le nombre d'itération.
C'est bien un algorithme en O(m).

[DonQuiche]

Je ne crois pas, le corrigé m'indique qu'elle est de : O(m log(mn))

Merci quand même ..

Je confirme que le corrigé est erroné, le premier problème est bien en O(m). C'est une simple boucle "for" courant de m à 1 (inclus).

Quant au second problème tel qu'il est écrit c'est une boucle infinie si n est initialement pair.Je présume que c'est une erreur de ta part et que "n%2=1" est ta condition de sortie. Dans ce cas c'est en O(ln(n)). En effet s commence à n puis vaut n/2, n/4, etc, jusqu'au premier nombre impair (exclus). Par exemple 24, 12, 6, 3. Dans le pire des cas ce sera jusqu'à n=1 et on aura donc effectué un nombre d'itérations i tel que n = (2^i), ce qui amène donc i = log2(n) et donc O(log2(n)). Et puisque les logarithmes sont identiques à une constante multiplicative près, on peut arbitrairement choisir d'écrire O(ln(n)) ou tout autre logarithme.

Calculer la complexité signifie calculer le nombre d'opérations nécessaires (en fonction des paramétrés d'entrée) pour exécuter l'algorithme.

Je suis désolé mais c'est moi qui ait désapprouvé le message. La raison en est avant tout que sur un plan pédagogique c'est nuisible : formulé ainsi un débutant va par exemple se demander combien d'instructions il y a dans "x = x + 1". Doit-il en compter une ou deux ? Et exprimé en assembleur x86, ça donne combien d'instructions ? Cette formulation à base de nombre d'instructions est problématique. Qui plus est elle attire l'attention à l'opposé du comportement asymptomatique qui nous intéresse.

Sur le plan formel c'est tout aussi faux. C'est pour les raisons auxquelles j'ai fait allusion que la complexité qui nous intéresse ici est définie en temps. Plus précisément en temps d'exécution par une machine de Turing quelconque, où le temps n'est exprimé qu'en fonction des dimensions du problème à l'aide de constantes indéterminées.

[Acrim]

Je suis désolé mais c'est moi qui ait désapprouvé le message. La raison en est avant tout que sur un plan pédagogique c'est nuisible : formulé ainsi un débutant va par exemple se demander combien d'instructions il y a dans "x = x + 1". Doit-il en compter une ou deux ? Et exprimé en assembleur x86, ça donne combien d'instructions ? Cette formulation à base de nombre d'instructions est problématique. Qui plus est elle attire l'attention à l'opposé du comportement asymptomatique qui nous intéresse.

Sur le plan formel c'est tout aussi faux. C'est pour les raisons auxquelles j'ai fait allusion que la complexité qui nous intéresse ici est définie en temps. Plus précisément en temps d'exécution par une machine de Turing quelconque, où le temps n'est exprimé qu'en fonction des dimensions du problème à l'aide de constantes indéterminées.

Le plus simple serait de proposer une définition qui te semble correct (d'un point de vue formel et pédagogique) car je ne suis pas sûr de saisir ce que tu veux dire.

En répondant j'avais en tête une définition du genre "La complexité (temporelle) d'un algorithme est le nombre d'opérations élémentaires (affectations, comparaisons, opérations arithmétiques) effectuées par un algorithme. Ce nombre s'exprime en fonction de la taille n des données." (http://www.enseignement.polytechniqu...w-poly009.html) Mais je suis dans doute un peu rouillé

[DonQuiche]

Le plus simple serait de proposer une définition qui te semble correct.

"Le temps nécessaire à l'exécution d'un algorithme, exprimé en fonction des dimensions du problème.

En pratique la complexité est exprimée pour une machine de Turing indéterminée à l'aide de constantes indéterminées, en ne s'intéressant qu'au comportement asymptotique. En général la complexité est exprimée pour le pire des cas mais selon les besoins elle peut aussi l'être pour le meilleur des cas ou le cas moyen."

"La complexité (temporelle) d'un algorithme est le nombre d'opérations élémentaires (affectations, comparaisons, opérations arithmétiques) effectuées par un algorithme. Ce nombre s'exprime en fonction de la taille n des données." (http://www.enseignement.polytechniqu...w-poly009.html) Mais je suis dans doute un peu rouillé

Je n'ai pas de lettre de crédit à présenter, je ne suis pas professeur à Polytechnique et je n'ai même pas de formation académique, mais je suis presque certain d'avoir raison en l’occurrence. Le nombre d'opérations est un détail lié à une architecture matérielle ou une écriture donnée (tel algo peut avoir six, douze ou vingt opérations selon le médium), et il faudrait encore considérer la durée de chaque opération, pas forcément homogènes, pour retrouver la complexité puisque cette dernière est une durée. Parler de nombre d'opérations introduit à mes yeux une abstraction obscure, mal définie et créant plus de problèmes qu'elle n'en résout.


Si on reprend le premier problème :

Code :

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

1
2
3
4
5
6
7
s <- m
r <- 0
 
While s >= 1
    r <- r+n
    s <- s-1
return r

Mieux vaut dire que si les opérations des deux premières lignes prennent un temps indéterminé A et que les opérations de la boucle prennent un temps indéterminé B, alors le temps total est A + m * B, dont le comportement asymptotique est O(m). Inutile de compter les opérations et de se demander si une addition est plus long qu'une assignation.

[Acrim]

D'accord.

Mieux vaut dire que si les opérations des deux premières lignes prennent un temps indéterminé A et que les opérations de la boucle prennent un temps indéterminé B, alors le temps total est A + m * B, dont le comportement asymptotique est O(m). Inutile de compter les opérations et de se demander si une addition est plus long qu'une assignation.

Si je comprends c'est le terme "opération" qui te pose problème ? Mais comme tu le dis ce qui est important c'est le comportement asymptotique. Que derrière le terme "opération élémentaire" se cache en réalité plusieurs opérations au niveau de processeur etc... peu importe, non ? Tout ce qui compte c'est que l'opération ne dépendent pas des paramètres d'entrée. Après, tu as peut-être raison sur le fait que ce soit moins pédagogique

[DonQuiche]

Si je comprends c'est le terme "opération" qui te pose problème ?

Plus précisément c'est leur dénombrement qui me pose problème. Chercher à les dénombrer n'apporte rien, est trompeur et pose de nombreuses questions.
En revanche le concept d'opérations lui-même n'est pas problématique ; il est d'ailleurs central au concept de machine de Turing et donc à tous nos processeurs.

Mais comme tu le dis ce qui est important c'est le comportement asymptotique.

Quand bien même, la notion de dénombrement des opérations n'apporte strictement rien.

Ensuite la complexité n'est pas toujours considérée du point de vue asymptotique, j'ai d'ailleurs soigneusement évité cette mention dans la définition formelle. Soit parce que les facteurs inférieurs sont dominants aux échelles pratiques (cas du raytracing contre le z-buffer), soit parce qu'on a besoin à l'exécution d'une approximation de la complexité pour prendre des décisions liées à l'optimisation (moteur de traitement des requêtes d'un SGBD). Et d'ailleurs dans ce dernier cas on ne compte pas les opérations assembleur qui seraient générées, là encore on utilise tout simplement des mesures temporelles.



EDIT : dernier problème, enseigner à dénombrer les opérations induit une mauvaise vision des problèmes de micro-optimisation. Dans la réalité il est souvent plus profitable de chercher à minimiser les transferts de données en privilégiant la localité plutôt que de se concentrer sur les instructions utilisées.

[Cocoffx]

Veuillez m'excuser... je crois que l'exercice ne parlait pas de la "complexité classique" mais de la complexité temporelle ..
Merci d'avoir pris du temps pour me répondre et encore désolé ..