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