Discussion :

[abidineb]

Bonjour a tous

J'ai compri globalement la notion 'complexite temporelle' grace a ce beau forum, mais je n'arrive pas a trouver la méthodologie d’évaluer un algorithme c'est a dire:
En ayant algorithme:

Code :

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

1
2
3
4
5
6
7
For i=1:40
i=i+1;
j=i;
end
if size(i)=size(j)
k=0;
end

Est ce que on met la complexite a cote des lignes de l'algorithme ou il y a une autre méthode universelle pour évaluer la complexite ligne par ligne??.

Merci

Cordialement

[abidineb]

Re
Peut être je n’étais pas bien explicite.
Je vais m'expliquer:
Dans un mémoire par exemple, On a l'algorithme déjà écrit, on veut évaluer ça complexite temporelle ligne par ligne, je veut juste savoir la façon de la faire.
Merci
Cordialement

[FR119492]

Salut!

Au risque de choquer certains, j'ai déjà exprimé sur ce site mes doutes sur le bien-fondé de la notion de complexité.

Si, néanmoins, tu veux calculer la complexité d'un algorithme, tu le programmes, puis tu traites des problèmes de taille différente et tu chronomètres.

Jean-Marc Blanc

[Franck Dernoncourt]

Si, néanmoins, tu veux calculer la complexité d'un algorithme, tu le programmes, puis tu traites des problèmes de taille différente et tu chronomètres.

Non, la complexité d'un algorithme est indépendante de son implémentation.

Est ce que on met la complexite a cote des lignes de l'algorithme ou il y a une autre méthode universelle pour évaluer la complexite ligne par ligne??.

Une ligne est O(1) sauf possiblement dans le cas d'une boucle ou d'un appel de fonction (il se peut que j'oublie des cas, le cas échéant faites-moi signe).

L'algorithme suivant est de complexité temporelle O(1) (c'est-à-dire constante) :

Code :

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

1
2
3
4
5
6
7
For i=1:40
i=i+1;
j=i;
end
if size(i)=size(j)
k=0;
end

PS @ abidineb : stp mets davantage d'accents sur les mots

[abidineb]

Bonsoir
Merci pour votre reponse, je pense que je n'arrive pas poser mon probleme , veuillez m'excuser, je ne cherche pas la solution de la complexite de cet algorithme....
Mais

Dans un rapport de travaux par exemple, j'ai mon algorithme ex: cet algorithme, pour évaluer sa complexité, j’écris

Code :

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

1
2
3
4
5
6
7
For i=1:40
i=i+1;                O(1)
j=i;                   O(1)
end
if size(i)=size(j)
k=0;                 O(1)
end

C'est a dire est ce qu'on met les complexite juste a cote des lignes de l'algorithme, ou il y a une autre façon conforme utilisé dans les rapports et travaux réalisés, j'ai beau cherché sur le net mais j'ai pas trouvé un exemple, comment analyser la complexite d'un algorithme.
Merci
Cordialement


PS @ abidineb : stp mets davantage d'accents sur les mots [/QUOTE]

[abidineb]

Bonsoir
Merci pour votre reponse, je pense que je n'arrive pas poser mon probleme , veuillez m'excuser, je ne cherche pas la solution de la complexite de cet algorithme....
Mais

Dans un rapport de travaux par exemple, j'ai mon algorithme ex: cet algorithme, pour évaluer sa complexité, j’écris

Code :

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

1
2
3
4
5
6
7
For i=1:40
i=i+1;                O(1)
j=i;                   O(1)
end
if size(i)=size(j)
k=0;                 O(1)
end

C'est a dire est ce qu'on met les complexite juste a cote des lignes de algorithme, ou il y a une autre façon conforme utilisé dans les rapports et travaux réalisés, j'ai beau cherché sur le net mais j'ai pas trouvé un exemple, comment analyser la complexite d'un algorithme.
Merci
Cordialement

[Franck Dernoncourt]

Je n'ai peut-être pas répondu assez explicitement : effectivement il faut analyser ligne par ligne, néanmoins toutes les lignes sont O(1) sauf possiblement dans le cas d'une boucle ou d'un appel de fonction (il se peut que j'oublie des cas, le cas échéant faites-moi signe).

Par conséquent, en pratique nous cherchons d'abord les boucles puis ce qu'elles contiennent. Si la taille d'une boucle dépend d'un paramètre de l'input de l'algorithme, par exemple for i = 1 to n, n étant la taille d'un tableau donné en input, alors la complexité de la boucle est O(n) pourvu qu'une itération est O(1), sinon la complexité de la boucle est O(1).

Il faudrait que tu trouves un cours ou des exemples détaillés sur la notion de complexité temporelle : je n'en ai pas sous la main pour les cas simples, il me semble que http://algo.developpez.com/livres/#L2100039229 donne quelques rappels mais pas sûr (par contre comme je l'ai dit ailleurs récemment, ce livre donne de bons conseils pour l'analyse de la complexité d'algorithmes plus subtils, e.g. faisant des appels récursifs) .

[abidineb]

Re

D’après ce que j'ai compris, la méthode c'est d’écrire les complexite devant les lignes du code de l’algorithme, donc c'est juste ou plutôt ils écrivent la complexite en dehors du code l’algorithme?
C'est ça, ce que je cherche, juste la méthodologie et pas le calcul de complexite
Merci
Cordialement

[Franck Dernoncourt]

Qu'appelles-tu écrire la complexite en dehors du code l’algorithme ?

[abidineb]

L1: O(1)
L1-L2: O(1)
L2-L3: O(1)
......

Est ce que ils font l’évaluation de cette façon sachant que L(ligne).
Merci
Cordialement

[Franck Dernoncourt]

Je ne vois pas de différence entre écrire en dehors de l'algorithme et dedans si ce n'est que dans le premier cas on fait appelle à une référence de ligne (L1) alors que dans le second cas nous n'en avons pas besoin. A moins que j'ai raté quelque chose ?

[abidineb]

Oui, c'est tout a fait ça, je cherche tout simplement la méthode la plus populaire pour l’évaluation, c'est ma problematique.
Merci, est ce que vous saisissez maintenant?
Cordialement

[Franck Dernoncourt]

De mon expérience personnelle, le fait d'écrire en dehors ou dans l'algorithme n'a aucune importance, et on ne fait pas ligne par ligne mais boucle par boucle, car une ligne est toujours trivialement O(1) sauf si boucle ou appel de fonction. Comme les boucles sont évidentes à analyser, en général on dit juste par exemple que la complexité temporelle de l'algorithme X est O(n²) car la boucle la plus couteuse a n itération et contient une boucle imbriquée de taille n également.

Ensuite les algorithmes qui intéressent les gens étudiant la complexité contiennent souvent des récurrences, des boucles à taille variable, etc, et là on commence à s'amuser :-)

[abidineb]

Merci pour tout.
Problème résolu.
Cordialement

[FR119492]

Salut!

Non, la complexité d'un algorithme est indépendante de son implémentation.

Mais ce qui compte, en pratique, c'est le temps de calcul, qui dépend de l'implémentation.
A titre d'exemple, le nombre d'opérations arithmétiques pour résoudre un système de n équations à n inconnues est un polynôme du 3ème degré en n. Mais le temps de calcul dépend de la place disponible en mémoire vive. Si celle-ci est insuffisante, le programme fera, sans te demander ton avis, des transferts sur disque qui prennent beaucoup de temps. J'ai fait jadis des tests qui montraient bien que le temps de calcul était une fonction discontinue de n.
Un autre exemple consiste à remplir une grosse matrice de termes tous identiques, par exemple des zéros. Le temps de calcul peut être très différent selon que tu remplis la matrice ligne par ligne ou colonne par colonne (et encore ça dépend si tu le fais en C ou en Fortran); le rôle de la complexité est donc marginal.
Jean-Marc Blanc

[Franck Dernoncourt]

Mais ce qui compte, en pratique, c'est le temps de calcul, qui dépend de l'implémentation.

Cela dépend si on se place du côté du concepteur de l'algorithme ou bien de l'utilisateur du logiciel. En outre, il faut garder en tête que l'objectif de l'étude des complexités est de comparer les différents algorithmes entre eux justement sans avoir à s'occuper des implémentations.

le temps de calcul dépend de la place disponible en mémoire vive.

C'est la raison pour laquelle les concepteurs d'algorithmes se penchent également sur la complexité spatiale.

Le temps de calcul peut être très différent selon que tu remplis la matrice ligne par ligne ou colonne par colonne

Memory thrashing

[abidineb]

Merci beaucoup, ça devient plus clair, mais je suis avec l'avis que la complexite temporelle et spatiale peuvent être utilisées pour une comparaison efficace des algorithmes, car on ne peut pas a chaque fois qu'on implémente un algorithme, on calcul ensuite son ton d'execution, pour évaluer sa rapidite.
Merci
Cordialement