Discussion :

[MysticKhal_0]

Bonjours,
Lorsque l'on parle d'algorithme, on parle souvent de complexité de celui-ci.
J'aimerais bien savoir comme la complexité d'un algorithme est calculée, et si par exemple il ce déroule plus rapidement etc.

Merci

[j.p.mignot]

Personnelement, je suis surtout impliqué par la performance d'un calcul qui suivant l'implémentation que l'on cherche doit optimiser la mémoire et/ou la vitesse d'execution et/ou la stack et/ou la taille du code lui même, ...
Il est rarement possible de gagner sur tous les aspects en même temps!

[MysticKhal_0]

Merci pour ce témoignage même s'il ne répond malheureusement pas à ma question...

En gros j'aimerais savoir dans quels cas on dit qu'un algo a une faible complexité, et dans quel cas on dit qu'il a une forte complexité, et éventuellement s'il faut privilégier tel ou tel complexité pour l'optimisation

[Wavyx]

en général on utilise la notation "big O" O(n) pour décrire la complexité. Je suppose que tu es familier avec cette notation. Ensuite, on peut définir des classes de complexité:
O(1) -> constante
O(log(n)) -> logarithmique
O(n) -> linéaire
O(n*log(n)) -> quasi-linéaire
O(n^2) -> quadratique
O(n^k) -> polynomiale (k doit être >1)
O(k^n) -> exponentielle

voilà en gros, quand un algo a une compléxité supra linéaire il est souvent "couteux". enfin n*log(n) et n^2 ou n^3 ça va encore (ça dépend du n )
mais exponentielle et plus, ça peut devenir gênant.
Attention toutefois, il n'est pas tjs possible de réduire la complexité d'un algorithme.
Un autre point à séparer de la complexité est l'optimisation du code lui-même (pas de l'algo): allocation mémoire, instantiations objets, structue de données, ...

j'espère que ça répond plus ou moins à ta question mais sinon il faudra être plus détaillé.

[MysticKhal_0]

Merci j'ai compris le système de notation grâce à toi

Donc en résumé, si je veux optimiser un aglo, avant les techniques "bourrins", j'essaye d'abors de chercher un algo de plus faible complexité?

[j.p.mignot]

Je ne suis pas tout à fait d'accord!!
L'optimisation en 'absolu', à mon avis, n'a pas de sens. Elle dépend des contraintes externes au problème - type de processeur, DSP, vitesse, quantité de mémoire, vitesse d'accès aux ports, ... -.
La plus part du temps le choix de l'algorithme, son degré de développement ou de 'factorisation', l'utilisation de récurrences qui montent parfois dramatiquement dans la stack,... sont AVANT tout une question de savoir OU le programme devra être implémenté.
Evidement sur un PC on ne se pose plus trop ce genre de question et on admet mémoire infinie, stack sans limite ( cela peut conduire à de belles surprises dans des calculs même très communs comme SORT, calcul de det, ... ) ...
En résumé, je préfère qualifier un algorithme en fonction de ses performances sv les moyens requis à son exécution et, le cas échéant, en avoir plusieurs versions suivant nécessité plutôt que de parler de complexité. Finalement le client d'un produit regarde le prix ( => optimisation sur les moyens à mettre en oeuvre), les performances ( choix des moyens nécessaires et pas + si non la possibilité d'intégrer les futurs développements que l'on envisage) mais, se préoccupe peu - si non PAS - de la complexité et du codage par lui même.

[Wavyx]

juste pour clarifier mon post, pour moi tu as
- complexité algo
- optimisation (souvent lié au code et aux contraintes "machine")

je ne pense pas avoir fait de lien tel que "complexité = optimisation".
Je pense que s'intéresser à la complexité dans le cadre de l'optimisation d'une méthode n'est pas forcément à exclure. si tu prends un algo de tri en O(n^3) tu peux clairement gagner en optimisation en choisissant un algo de tri plus classique et moins coûteux (bien sûr il peut y avoir des contraintes de mémoire par ex)
sinon c'est vrai que s'il s'agit d'optimisation, il faut parfois envisager des solutions liées au code lui même, au language et à ses spécificités,... et d'autre part l'environnement "physique" sur lequel il tourne (ce qui ressort nettement de ton post dsp, vitesse d'accès, ...)

enfin je suis d'accord pour le fait que l'optimisation est impossible à définir en absolu. C'est pour moi en quelque sorte trouver le "meilleur" compromis entre la tâche à accomplir et comment elle est accomplie.

Il faudrait plus de détails pour savoir exactement le cadre du problème d'optimisation de NecroMagik

[j.p.mignot]

OK!
en fait j'ai plutôt réagit à la réponse
"si je veux optimiser un aglo, ... j'essaye d'abors de chercher un algo de plus faible complexité"

Pour le reste il est evidant qu'1 algo en O(n^2) est mailleur à un autre en O(n^3) SI son implementation est compatible avec les 'moyens du bord'!
Par ailleur, dans bien des cas, comme fit moinre carrés,résolution d'équation différentielles, ...le nombre de cyles requis est imprédictible et est fonction du modéle et des points expérimantaux, de la reésolution souhaitée... (O^n=? devient alors délicat à estimer )

[Jean-Marc.Bourguet]

Merci j'ai compris le système de notation grâce à toi

Donc en résumé, si je veux optimiser un aglo, avant les techniques "bourrins", j'essaye d'abors de chercher un algo de plus faible complexité?

Pas sûr. D'abord, la complexité te donne le comportement pour une taille de problème suffisemment grande. Il est possible que pour les tailles qui t'intéressent, l'algo ayant le meilleur comportement asymptotique se comporte en fait très mal.

Ensuite, si on parle de complexité sans préciser, on parle du pire des cas. Il est des algo dont le comportement moyen est nettement meilleur que celui dans le pire des cas. Suivant le contexte, on peut désirer employer ou non un algo dont le comportement moyen est bon même s'il existe d'autres algo pour le même problème avec un meilleur comportement dans le pire des cas (par exemple parce qu'on peut prouver qu'on n'est jamais dans le pire des cas).

[MysticKhal_0]

A vrai dire je n'est pas de cas précis sous la main car je débute en algorithimie..
J'ai néanmoins lu que l'idéal au niveau de l'optimisation serait d'abord de trouver un algo de complexité moindre (après bien sur qu'il peut y avoir des changements au niveau de la structure des données par exemple). Mais il semble évisent qu'un algo de complexité logarithmique soit plus rentable qu'un exponentiel non? (Je parle d'un cas général, bien sur qu'il peut y avoir des exeptions) ^^

[xxiemeciel]

tu peux auss optimiser tes algorithmes sans changer la complexité en optimisant les techniques de calculs

une addition/soustraction sera plus rapide que multiplication/division. Ou encore faire des decalage de bits ...

un bon exemple est l'optimisation de l'algorithme de bresenham, ceci dit avant d'optimiser il est quand meme plus interessant de prendre la meilleure complexité au depart .

XXiemeciel

[méphistopheles]

Je suis peut-être à coté de la plaque mais par simple curiosité, y-ast'il une complexité associée aux fonctions récursives (qui sont toujours linéarisables) et si oui, laquelle.


salut

[Jean-Marc.Bourguet]

A vrai dire je n'est pas de cas précis sous la main car je débute en algorithimie..
J'ai néanmoins lu que l'idéal au niveau de l'optimisation serait d'abord de trouver un algo de complexité moindre (après bien sur qu'il peut y avoir des changements au niveau de la structure des données par exemple). Mais il semble évisent qu'un algo de complexité logarithmique soit plus rentable qu'un exponentiel non? (Je parle d'un cas général, bien sur qu'il peut y avoir des exeptions) ^^

La complexité est un des facteurs qui intervient dans le temps de calcul. Un autre est la constante. Un autre est le fait que la taille des donnée peut être dans une zone ou l'algo n'a pas encore son comportement asymptotique. Un autre est la difficulté de l'implémentation. Vouloir favoriser un aspect au dépend des autres n'est pas très utile en pratique. Il faut regarder le contexte et faire un compromis entre les différentes contraintes (techniques et autres).

[Jean-Marc.Bourguet]

Je suis peut-être à coté de la plaque mais par simple curiosité, y-ast'il une complexité associée aux fonctions récursives (qui sont toujours linéarisables) et si oui, laquelle.

Oui, on peut calculer la complexité d'une fonction récursive (enfin, de certaines d'entre elles). Non les fonctions récursives ne sont pas toujours linéarisables.

[FrancisSourd]

Vouloir favoriser un aspect au dépend des autres n'est pas très utile en pratique. Il faut regarder le contexte et faire un compromis entre les différentes contraintes (techniques et autres).

A titre d'exemple, la procédure de tri réputée la plus performante est le quicksort qui tourne en O(n^2) alors qu'il existe des procédure en O(n logn).
Toutefois, il est possible de montrer que la complexité en moyenne du quicksort est en O(n logn) et en plus, il est relativement simple à implanter en nécessite peu de recopies mémoire.

L'instance joue aussi un rôle: le quick sort n'est pas l'algorithme le plus efficace lorsque le tableau d'entrée est déjà "presque" trié. De même, s'il y a beaucoup de doublons et que les valeurs sont relativement petites (valeurs entre 0 et 100 par exemple) un tri par buckets est à mon avis meilleur.

[méphistopheles]

Oui, on peut calculer la complexité d'une fonction récursive (enfin, de certaines d'entre elles). Non les fonctions récursives ne sont pas toujours linéarisables.

heu, je ne suis pas renseigné, mais mon professeur de maths m'a dis qu'il existais une démonstration prouvant que TOUTES les fonctions récursives étaient linéarisable.
il m'a même affirmé qu'il existais de "linéariseurs" de fonctions.

pour ma part, je n'affirme rien.


salut

[Jedai]

De toute façon si on y réfléchit une seconde, les fonctions récursives sont forcément linéarisables, puisque l'ordinateur est lui même une machines aux processus itératifs et qu'il exécute tes fonctions "récursives".... En fait il suffit de savoir gérer une pile pour pouvoir linéariser n'importe quelle fonction, maintenant cela ne signifie pas le faire de façon efficace (par exemple il existe une solution itérative aux tours de Hawaï qui est beaucoup plus intelligente qu'une simple transformation en boucle avec une pile), j'imagine qu'il y a beaucoup mieux.

(Pour une réponse plus convaincante, voire les démonstrations d'équivalence des modèles de calculabilité, notamment la machine de Turing (intrinsèquement itérative) et les fonctions récursives primitives (sur lesquelles a travaillé par exemple Gödel))

(EDIT : Dans tout cela j'ai assumé que linéarisation signifiait le processus que je connais mieux sous le nom de "dérécursification", autrement dit transformer un processus récursif en un processus itératif équivalent. Je dois cependant dire que j'ai rarement vu "linéarisation" utilisé ainsi (en fait jamais), et je n'ai aucune idée si cela est correct ou non, mais le contexte m'a incité à l'interpréter ainsi, j'espère ne pas m'y être trompé : il est par exemple évident qu'un algorithme récursif n'est pas forcément de complexité linéaire... )

--
Jedaï

[méphistopheles]

pour moi, la linéarisation d'une fonction récursive consiste en sa transformation en une fonction ne contenant que des boucles et des instructions successives et ayant un nombre limité et prédéfini de variable.
par exemple,lorsqu'on linéarise la methode d'euclide (pour trouver le pgcd et les coefficient de corespondance si pgcd =1) on utilise 5 variable seulement alors que la fonction comporte un nombre indéfini de degrés de récursivité.

salut

[PRomu@ld]

On a vu en, algo cette année que toute fonction récursive a son équivalent en itératif. (plus ou moins facilement). Le principe général repose sur l'utilisation d'une pile, et comme l'a dis Jedai, celà revient en fait à simuler ce qui se passe dans l'ordinateur. Et nous aussi, nous l'avons appelés dérécursification

par exemple il existe une solution itérative aux tours de Hawaï

Ca ne serait pas les tours de Hanoï ?

Pour en revenir aux complexités, il ne faut pas toujours utiliser la notation grand O car c'est un majorant et ne montre pas forcément l'allure d'une fonction. (une fonction en O(n) est aussi une fonction en O(n^2)). Il vaut mieux utiliser la fonction sigma qui là nous donne plus d'information sur le comportement des fonctions.

Pour ce qui est de la calculabilité d'une fonction récursive, c'est assez simple, en fait il suffit la plupart du temps d'établir la relation de récurence et ensuite on trouve la complexité simplement. (ce ne sont que des maths basiques la plupart du temps)

[Trap D]

Un bon exo est de dérécursiver la fonction d'Ackermann :

Code :

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

1
2
3
4
5
La fonction d'Ackermann est la fonction définie sur les couples d'entiers naturels par les formules de récurrence suivante : 
A(0,n)=n+1 
A(m,0)=A(m-1,1) 
A(m,n)=A(m-1,A(m,n-1)) 
  La fonction d'Ackermann est très compliquée à calculer, car très récursive. Son calcul sur un ordinateur conduit souvent au débordement de la pile!

Il em semble qu'on en a déjà parlé ici.