Existe-t-il une différence entre complexité de calcul et complexité d'implémentation?

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.

Salut!

Citation:

---

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

Citation:

---

Envoyé par FR119492

[...] 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.

Bonjour,

Citation:

---

Envoyé par saou88

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.

Citation:

---

Envoyé par Aleph69

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.

Citation:

---

Envoyé par FR119492

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. :D

Salut davcha,

Citation:

---

Envoyé par 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?

Citation:

---

Envoyé par davcha

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.

Bonjour,

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

Citation:

---

Envoyé par saou88

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 :

Citation:

---

Envoyé par saou88

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.

Citation:

---

Envoyé par saou88

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

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

Citation:

---

Envoyé par kwariz

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.

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

Citation:

---

Envoyé par 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 stabilité comme tu l'as implicitement souligné avec l'exemple de l'algorithme de Strassen!

Citation:

---

Envoyé par FR119492

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.

Citation:

---

Envoyé par FR119492

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.

Citation:

---

Envoyé par 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,

---

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

Citation:

---

Envoyé par FR119492

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.

Citation:

---

Envoyé par FR119492

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.

Citation:

---

Envoyé par Aleph69

[...]
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.

Citation:

---

Envoyé par kwariz

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.

Citation:

---

Envoyé par Aleph69

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

Citation:

---

Envoyé par kwariz

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

:D

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. :D

Citation:

---

Envoyé par souviron34

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.

Citation:

---

Envoyé par souviron34

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

Citation:

---

Envoyé par souviron34

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

Citation:

---

Envoyé par souviron34

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

:D

---

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.

Citation:

---

Envoyé par Aleph69

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:

---

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

Citation:

---

Envoyé par Aleph69

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:

---

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

Citation:

---

Envoyé par souviron34

Code:

---

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)

Citation:

---

Envoyé par souviron34

Code:

---

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

Citation:

---

Envoyé par souviron34

Code:

---

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.

Citation:

---

Envoyé par souviron34

Code:

---

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.

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

Citation:

---

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

---

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

Citation:

---

Envoyé par souviron34

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.

Citation:

---

Envoyé par souviron34

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