Discussion :

[saou88]

Salut tout le monde,
Ma question semblerait peut -être un peu bizarre ou peut être fera-t-il un sens pour certains.
En fait, je veux m'assurer du fait qu'il y ait ou pas une différence entre la complexité de calcul qu'engendrerait un algorithme et puis son implémentation sur machine. Par exemple, si deux algo ont une même complexité de calcul, l'un peut-il avoir une caractéristique d'être plus facile à implémenter?

PS. J'ai trouvé cette remarque dans un article, mais elle est brève sans aucune explication et je tiens à m'assurer de sa validité.

Merci.

[FR119492]

Salut!

différence entre complexité de calcul et complexité d'implémentation

Je ne connaissais pas ces deux termes, mais je peux te raconter une expérience que j'ai faite il y a quelques années: j'avais fait un programme pour chronométrer le temps nécessaire pour factoriser une matrice et le représenter en fonction de la taille de la matrice. Théoriquement, la complexité de l'algorithme utilisé était telle que le graphe aurait dû être une cubique. En réalité, c'était loin d'être le cas. D'une part, il y avait une forte dispersion: pour la même matrice, on trouvait des temps assez différents, probablement parce que le processeur de mon ordinateur faisait d'autres choses en même temps. D'autre part, le graphe présentait une discontinuité inattendue; je suppose qu'elle provenait du fait qu'à partir d'une certaine taille il y avait des transferts de données vers le disque dur. Cette expérience m'a convaincu que la notion de complexité, en théorie, c'était très joli, mais qu'en pratique, ça ne servait pas à grand chose.
Jean-Marc Blanc

[kwariz]

[...] Cette expérience m'a convaincu que la notion de complexité, en théorie, c'était très joli, mais qu'en pratique, ça ne servait pas à grand chose.
Jean-Marc Blanc

Bonjour,

c'est comme tous les outils, mal utilisés ils sont inutiles. Utiliser «le bon algorithme» ne consiste pas uniquement à en regarder la compléxité asymptotique en temps.
Je prends le terme compléxité d'implémentation comme «la difficulté à implémenter un algorithme sur une plateforme particulière dans un langage particulier par une personne particulière.
Quand on décide de l'utilisation d'un algorithme c'est non seulement parce qu'il est adapté au problème à résoudre, aux données réelles qu'il va devoir traiter mais aussi parce qu'on dispose de structures de données adaptées, des connaissances suffisantes pour le faire, de suffisamment de temps pour le faire (que l'on soit seul ou que l'on travaille en équipe).
Essayer d'utiliser à chaque instant et à tout endroit l'algorithme de meilleure complexité est en soi un hérésie (à mon sens) cela amène souvent à un code spaghetti, une usine à gaz non maintenable quand (enfin si) ça fonctionne.

[Aleph69]

Bonjour,

Par exemple, si deux algo ont une même complexité de calcul, l'un peut-il avoir une caractéristique d'être plus facile à implémenter?

Ta question n'a pas de sens tant que tu n'as pas rigoureusement défini une relation d'ordre entre deux algorithmes du type "algo A est plus facile à implémenter que algo B". La notion de facilité d'implémentation est bien trop subjective. Si tu devais réellement implémenter un algorithme de A à Z, c'est-à-dire sans utiliser aucune bibliothèque standard, extérieure ou aucune fonction prédéfinie d'aucun langage, tu n'y arriverais peut-être même pas dans la plupart des cas. J'entends par là que la facilité d'implémentation que tu évoques dépend du niveau d'implémentation où tu te places. Un algorithme pourra te sembler très facile à implémenter à un haut niveau alors que tu aurais trouvé l'implémentation des fonctions bas niveau trop difficiles à ton goût.

[davcha]

Bonjour,



Ta question n'a pas de sens tant que tu n'as pas rigoureusement défini une relation d'ordre entre deux algorithmes du type "algo A est plus facile à implémenter que algo B". La notion de facilité d'implémentation est bien trop subjective. Si tu devais réellement implémenter un algorithme de A à Z, c'est-à-dire sans utiliser aucune bibliothèque standard, extérieure ou aucune fonction prédéfinie d'aucun langage, tu n'y arriverais peut-être même pas dans la plupart des cas. J'entends par là que la facilité d'implémentation que tu évoques dépend du niveau d'implémentation où tu te places. Un algorithme pourra te sembler très facile à implémenter à un haut niveau alors que tu aurais trouvé l'implémentation des fonctions bas niveau trop difficiles à ton goût.

Tu supposes que la dérivée de ta fonction d'ordre par rapport au niveau d'implémentation (comme tu dis) change en fonction de l'algorithme, là...

Prise de tête tout ça.

Je pense qu'on pouvait répondre : oui, il existe une différence, dans la mesure où la notion de "complexité de calcul" (temporelle ou spatiale) est différente de la notion de difficulté d'implémentation qui est de toute façon subjective.

[pseudocode]

Cette expérience m'a convaincu que la notion de complexité, en théorie, c'était très joli, mais qu'en pratique, ça ne servait pas à grand chose.

En pratique, ca a permis de montrer que:
1. la complexité serait "au mieux" cubique.
2. le hardware/software était un facteur limitant pour atteindre les performance attendues.

Pas si mal pour un truc qui ne sert pas a grand chose.

[Aleph69]

Salut davcha,

Tu supposes que la dérivée de ta fonction d'ordre par rapport au niveau d'implémentation (comme tu dis) change en fonction de l'algorithme, là...

Je ne comprends pas le sens de ta phrase. Qu'appelles-tu une fonction d'ordre?

Je pense qu'on pouvait répondre : oui, il existe une différence, dans la mesure où la notion de "complexité de calcul" (temporelle ou spatiale) est différente de la notion de difficulté d'implémentation qui est de toute façon subjective.

Sauf erreur de ma part, tu as écrit : "il existe une différence entre A et B parce que A est différent de B".

Il est nécessaire de définir clairement de quoi on parle pour pouvoir prouver le vrai ou le faux. Sans quoi, on aboutit à des affirmations qui peuvent apparaître à première vue évidentes mais qui sont finalement dépourvues de sens.

[kwariz]

Bonjour,

Le premier message est confus car on peut l'interpréter de manière différente. La première vient de la partie :

En fait, je veux m'assurer du fait qu'il y ait ou pas une différence entre la complexité de calcul qu'engendrerait un algorithme et puis son implémentation sur machine.

Que l'on peut interpréter comme : si on a un algo en O(f(n)) est-on certain que son implémentation sera réellement en O(f(n)), c'est-à-dire si on crée un graphique du genre [taille entrée]/[temps effectivement pris pour la résolution]
alors ce graphique aura-t-il bien la bonne forme prédite ?
La réponse est à la fois oui et non.
Le non s'explique simplement. Quand on étudie la complexité algorithmique d'un algo, celle-ci donne un comportement asymptotique. Mais ce qui est important est de remarquer que la compleité algorithmique considère, par exemple, que l'accès mémoire se fait en temps constant quelle que soit la taille d'un tableau. Ce qui dans les faits est totalement faux. Autant on peut considérer le temps d'accès en RAM constant dans une certaine mesure, autant il y a des mécanisme qui soit font que l'accès est plus rapide (mémoire cache, lecture de données proches ou peu de données => plus rapide), soit font que l'accès est plus lent (beaucoup de données, accès à des données éloignées => plus lent). Donc le graphique va certainement présenter des sauts.
Ce n'est qu'un exemple, j'aurai pu aussi citer la difficulté de chronométrer précisément le temps d'exécution, ou les optimisations des compilos ou même des différences entre langage (c=lecture d'un tableau par ligne, fortran=lecture d'un tableau par colonnes).
Non aussi pour des raisons non physiques : si on essaye de créer un graphe de performances de quicksort on ne verra pas une courbe mais un nuage de points délimité par deux courbes (cas favorable en n.lg n et cas défavorable en n).
Enfin la partie oui, car dans les morceaux où les hypothèses comme temps d'accès constant sont vraies alors oui, la courbe aura bien la bonne forme.
Une étude de complexité n'est pas juste un exercice, c'est une donnée utile.

Tout ce que j'ai dit sur la complexité en temps est tout aussi valable en complexité en espace.



La seconde interprétation vient de la question qui suit :

Par exemple, si deux algo ont une même complexité de calcul, l'un peut-il avoir une caractéristique d'être plus facile à implémenter?

Ici le PO parle de "plus facile" à implémenter. Comme ça a été dit, la difficulté à implémenter est très subjective et très dépendante de l'environement d'implémentation, de celui qui inplémente, mais aussi de celui qui a écrit l'algo en fin de compte.
Une personne qui a l'habitude du C ne produira pas généralement le même type de pseudo code que quelqu'un qui a l'habitude de Matlab par exemple.
Les notations seront forcément teintées par le background de celui qui écrit.

Mais peut-être le PO confond-il les deux notions : complexité d'un algo = difficulté à l'écrire : ce qui est totalement faux.

PS. J'ai trouvé cette remarque dans un article, mais elle est brève sans aucune explication et je tiens à m'assurer de sa validité.

Merci.

Peut-être pourrais-tu nous donner les références de cet article (ou à défaut nous écrire le passage)


PS: en relisant je remarque que l'exemple de quicksort est un vrai bon mauvais exemple. En effet lorsqu'on donne une complexité d'un algo de tri par comparaisons cette conplexité mesure le nombre de comparaisons ...

[Franck Dernoncourt]

FYI http://www.developpez.net/forums/sea...archid=8628225

[Invité]

Le non s'explique simplement. Quand on étudie la complexité algorithmique d'un algo, celle-ci donne un comportement asymptotique. Mais ce qui est important est de remarquer que la compleité algorithmique considère, par exemple, que l'accès mémoire se fait en temps constant quelle que soit la taille d'un tableau. Ce qui dans les faits est totalement faux.

Ce genre de choses peut être pris en compte dans les calculs de complexités asymptotiques. Aujourd'hui, on sait évaluer le nombre de cache miss/page miss effectués par un programme, et en déduire une complexité. Et on peut même créer des algorithmes de haut niveau qui cherchent à diminuer au maximum ces complexités. Ça s'appelle des cache oblivious algorithms. Donc, d'un point de vue formel, les accès mémoires en eux-mêmes ne changent pas la complexité asymptotique d'un algorithme. On se retrouve simplement avec deux complexités : une qui mesure le nombre d’opérations arithmétiques, et une autre pour les caches miss : il suffit de prendre la plus grande pour obtenir la bonne complexité.

Après, il y a bien des trucs qui vont venir perturber ce beau monde : les divers mécanismes de data prefetching peuvent faire varier les complexités asymptotiques de certains codes, du moins pour la complexité en cache/page miss. Mis pour être franc, c'est rare, et à part quelques cas simples (itération dans un tableau), je n'ai pas d'exemples. Il faut dire qu'à part dans des algorithmes dans lesquels on pré-calcule beaucoup de choses, il est rare d'avoir une complexité asymptotique bornée supérieurement par la complexité en cache miss et pas par la complexité des opérations arithmétiques.

[FR119492]

Bonjour à tous!
Ce qui compte réellement, lorsqu'on choisit un algorithme, c'est seulement le temps que le programme prendra pour effectuer les calculs, et la connaissance de la complexité des divers algorithmes peut nous donner des idées pour effectuer notre choix; par exemple, si on doit résoudre un système de 10'000 équations à 10'000 inconnues, on ne choisira pas la méthode de Sarrus. Mais on ne choisira pas non plus celle de Strassen, bien que sa complexité soit inférieure à celle des méthodes "classiques". D'autre part, la méthode de Cholesky est presque deux fois plus rapide que celle de Gauss-Jordan, bien qu'elle ait la même complexité.
Un autre problème est aussi significatif: remplir une matrice de très grande taille: en Fortran, ça va plus vite si on la parcourt colonne par colonne, alors qu'en C, il vaut mieux le faire ligne par ligne. Alors, quel rôle joue la complexité?
Jean-Marc Blanc

[Aleph69]

Bonjour à tous!
Ce qui compte réellement, lorsqu'on choisit un algorithme, c'est seulement le temps que le programme prendra pour effectuer les calculs

... et la stabilité comme tu l'as implicitement souligné avec l'exemple de l'algorithme de Strassen!

D'autre part, la méthode de Cholesky est presque deux fois plus rapide que celle de Gauss-Jordan, bien qu'elle ait la même complexité.

En fait si tu regardes la constante devant le terme en n^3, tu trouveras respectivement 1/3 et 2/3, ce qui explique ta remarque.

Un autre problème est aussi significatif: remplir une matrice de très grande taille: en Fortran, ça va plus vite si on la parcourt colonne par colonne, alors qu'en C, il vaut mieux le faire ligne par ligne. Alors, quel rôle joue la complexité?

Cela rejoint l'intervention de mewtow (très intéressante au passage) : tout dépend de la manière dont tu calcules la complexité. En général, on fait beaucoup d'hypothèses simplificatrices mais libre à toi de ne pas les faire.

[kwariz]

Bonjour à tous!
Ce qui compte réellement, lorsqu'on choisit un algorithme, c'est seulement le temps que le programme prendra pour effectuer les calculs,

On ne choisit pas un algo, on choisit d'implémenter un algo et tout ce qui va avec (entre autre les structures adaptées) pour obtenir le résultat escompté (car l'algo a été vérifé formellement : il est correct, il termine, etc ..). Le souci d'avoir une version rapide n'est jamais obligatoire, on peut aussi se soucier de minimiser d'autres ressources que le temps (la mémoire, les accès coûteux à des ressources externes, tout dépend de ce qu'on mesure).

et la connaissance de la complexité des divers algorithmes peut nous donner des idées pour effectuer notre choix; par exemple, si on doit résoudre un système de 10'000 équations à 10'000 inconnues, on ne choisira pas la méthode de Sarrus. Mais on ne choisira pas non plus celle de Strassen, bien que sa complexité soit inférieure à celle des méthodes "classiques". D'autre part, la méthode de Cholesky est presque deux fois plus rapide que celle de Gauss-Jordan, bien qu'elle ait la même complexité.

Tu parles d'implémentations pas d'algorithmes. La complexité d'un algo est un outil théorique qui peut donner non seulement des indications d'utilisations mais aussi des contre indications. Après il s'agit parfois d'expérience et de savoir-faire. Il est tout autant ridicule de vouloir toujours utiliser heapsort pour trier un tableau sous prétexte qu'il a le meilleur comportement même dans le pire des cas et pour justifier par là même qu'on ne peut faire mieux vu qu'on a utilisé le meilleur algo de dispo.

Un autre problème est aussi significatif: remplir une matrice de très grande taille: en Fortran, ça va plus vite si on la parcourt colonne par colonne, alors qu'en C, il vaut mieux le faire ligne par ligne. Alors, quel rôle joue la complexité?
Jean-Marc Blanc

À nouveau il s'agit de problèmes d'implémentations, donc ici la complexité algorithmique ne joue aucun rôle particulier : peu importe les diff de perf entre c/ligne fortran/colonne l'algo aura toujours le même comportement.

[kwariz]

[...]
Cela rejoint l'intervention de mewtow (très intéressante au passage) : tout dépend de la manière dont tu calcules la complexité. En général, on fait beaucoup d'hypothèses simplificatrices mais libre à toi de ne pas les faire.

Ce ne sont pas des hypothèses simplificatrices mais des modèles (machine RAM ou machine de Turing, ou d'autres encores). La différence c/fortran est une différence d'implémentation pas de modèle à proprement parler.

[Aleph69]

Ce ne sont pas des hypothèses simplificatrices mais des modèles (machine RAM ou machine de Turing, ou d'autres encores). La différence c/fortran est une différence d'implémentation pas de modèle à proprement parler.

Dans les calculs de complexité, on fait souvent des hypothèses implicites du genre "toutes les opérations arithmétiques ont le même coût", "tous les accès mémoire ont le même coût", etc. Tu peux très bien effectuer un calcul de complexité en faisant le moins d'hypothèses possibles, cela va juste compliquer l'analyse mais rien ne t'empêche. Un modèle est justement un ensemble d'hypothèses.

[kwariz]

Dans les calculs de complexité, on fait souvent des hypothèses implicites du genre "toutes les opérations arithmétiques ont le même coût", "tous les accès mémoire ont le même coût", etc. Tu peux très bien effectuer un calcul de complexité en faisant le moins d'hypothèses possibles, cela va juste compliquer l'analyse mais rien ne t'empêche. Un modèle est justement un ensemble d'hypothèses.

Évidemment, je pinaillais un peu. tous les modèles qu'on utilise sont de grossières simplifications du réel
Néanmoins je fais une différence essentielle entre les problèmes liés à l'implémentation d'un algorithme (et de tout ce qui va avec, ok je pinaille) sur une architecture particulière et ce qu'on appelle sa complexité. C'était une "bonne surprise" de prouver que PRIMES est dans P, mais ça ne donne pas pour autant une implémentation révolutionnaire.
La complexité d'un algo donne le comportement asymptotique d'un algorithme suivant une mesure dans un modèle, mais que des indications sur les performances d'une implémentation particulière sur une plateforme particulière etc ...

[souviron34]

La complexité d'un algo donne le comportement asymptotique d'un algorithme suivant une mesure dans un modèle, mais que des indications sur les performances d'une implémentation particulière sur une plateforme particulière etc ...

voui...

C'est pas si évident que ça non plus....

Prenons un algo en O(N) où à chaque étape on calcule un log.

Même si la complexité arithmétique est en O(N), si je ne dispose que d'une machine qui calcule les logs par série de Taylor, je peux très bien me retrouver avec un algo équivalent à un en O(N2) sur cette machine...

Maintenant, prenons un allgo en O(N2) mathématiquement, mais qui comprend 10 parties suivantes en O(N).

Si la partie en O(N2) est simplement une addition et que les parties en O(N) font 100 divisions chacune, vraisemblablement la vraie complexité sera en O(N)..

Donc le "comportement asymptotique" est là aussi flou suivant la manière dont on le regarde..

[pseudocode]

Oui, enfin...

• La définition usuelle de la complexité informatique c'est l'étude de la consommation des ressources (cpu, mémoire) en fonction du volume de données à traiter.
  
• La complexité "algorithmique" s'abstrait des variations dues à l'implémentation, généralement en posant des hypothèses sur la consommation des opérations élémentaires.
  
• La notation O() montre le comportement asymptotique, lorsque le volume de données à traiter tend vers l'infini.

La complexité algorithmique en notation O() n'est donc pas si floue que cela.

[Aleph69]

Prenons un algo en O(N) où à chaque étape on calcule un log.

Même si la complexité arithmétique est en O(N), si je ne dispose que d'une machine qui calcule les logs par série de Taylor, je peux très bien me retrouver avec un algo équivalent à un en O(N2) sur cette machine...

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.

Maintenant, prenons un allgo en O(N2) mathématiquement, mais qui comprend 10 parties suivantes en O(N).

Si la partie en O(N2) est simplement une addition et que les parties en O(N) font 100 divisions chacune, vraisemblablement la vraie complexité sera en O(N)..

Donc le "comportement asymptotique" est là aussi flou suivant la manière dont on le regarde..

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

[kwariz]

voui...

C'est pas si évident que ça non plus....

Prenons un algo en O(N) où à chaque étape on calcule un log.

Même si la complexité arithmétique est en O(N), si je ne dispose que d'une machine qui calcule les logs par série de Taylor, je peux très bien me retrouver avec un algo équivalent à un en O(N2) sur cette machine...

Bonjour,
Effectivement ce n'est pas si évident que ça. Il faut d'abord savoir ce qu'on mesure, je suppose ici que N représente la taille d'un tableau de flottants par exemple. On dispose d'un algorithme en O(N) pour résoudre un problème particulier. La mesure de la complexité a été faite en prenant la calcul du log en O(1).
Le calcul d'un log par série de Taylor peut-être implémenté en O(k^2) où k est le nombre de bit nécessaires pour représenter un réel. On prendra un algo pour calculer une série de Taylor en O(n^1/2 M(n)), où M(n) est la compléxité de l'algo de multiplication, par exemple M(n)=O(n^1.465).
L'algorithme sera donc a priori en O(N.k^2).

Maintenant, prenons un allgo en O(N2) mathématiquement, mais qui comprend 10 parties suivantes en O(N).

Si la partie en O(N2) est simplement une addition et que les parties en O(N) font 100 divisions chacune, vraisemblablement la vraie complexité sera en O(N)..

Donc le "comportement asymptotique" est là aussi flou suivant la manière dont on le regarde..

Il n'y a pas de "vraie" complexité, même si effectivement on pourrait faire un rapprochement entre complexité "ressentie" et complexité comme en météo on le fait entre température mesurée et température ressentie.

Si séquentiellement une opération en O(n^2) est suivie même par un milliard d'opérations en O(n) (ou O(log n) ou O(1)), la complexité de l'algorithme sera en O(n^2). Au bout d'un moment. n^2 finira par dominer ce qui suit. La notation grand O permet de se détacher de ces préjugés subjectifs.

Ensuite il y a aussi les complexités dans le pire des cas, la complexité en moyenne qui ne mesurent pas forcément la même chose.

Si on ne regarde pas le comportement asymptotique, effectivement le comportement sera plus linéaire. Un peu comme on peut approximer sin x par x quand x est suffisament petit et dire que sinus est linéaire au voisinage de 0.

Quand on cherche à déterminer la complexité les constantes on s'en fout, quand on cherche à implémenter on s'en fout moins mais elles dépendent fortement des outils qu'on utilise.