Discussion :

[an1981]

bonjour tout le monde, mon probleme est le calcul de complexité d'un algorithme dans le cas où celle ci est logarithmique (O(log(n))) ou exponentielle. plus exactement je veux savoir s'il ya une manière pour savoir que tel algorithme est de complexité logarithmique ou exponentielle?.

**est ce que ça se fait de la meme manière que pour la complexité polynomiale ? ou bien il faut analyser l'algorithme autrement? et est qu'il ya parmi les algorithmes de tri ceux dont la complexité est exponentielle?

merci d'avance

[ToTo13]

Bonjour,

mon probleme est le calcul de complexité d'un algorithme dans le cas où celle ci est logarithmique (O(log(n))) ou exponentielle. plus exactement je veux savoir s'il ya une manière pour savoir que tel algorithme est de complexité logarithmique ou exponentielle?.

Alors en répondant de manière un peu brute à la question :
- tu auras du logarithme si à chaque itération de ton algorithme, tu divises ton espace de travail (cf. recherche dichotomique). En revanche, un tri comme le QuickSort a un complexité dans le pire des cas en O(N^2), mais en O(N log N) en moyenne !!!
De même, dans le tri par tas (HeapSort me semble t-il), à chaque itération tu "entasses" ton tableau et ceci se fait en O(Log N) car tu parcours les branches d'un arbre binaire. Donc ton espace de travail est divisé.
- pour l'exponentielle, tu l'obtiens lorsque tu dois chercher toutes les combinaisons possibles à chaque itérations. Par exemples, si tu souhaites faire toutes les combinaisons possible des sous ensemble d'un ensemble d'élément (un élément de l'ensemble est présent ou non), tu auras une complexité en O(2^N), avec N le nombre d'éléments dans l'ensemble.

est qu'il ya parmi les algorithmes de tri ceux dont la complexité est exponentielle?

Curieusement oui, mais c'est tellement invraissemblable de le décrire que peu de personnes en connaisse un.
Et bien c'est très simple :
- Enumérer TOUTES les combinaisons possibles de classement de tes éléments O(N^N). (Chaque élément pouvant aller à toutes les places)
- Pour chaqu'une des combinaisons, vérifier si le tri est bon (si l'élément I est plus petit que l'élement I+1).

[an1981]

merci pour votre reponse mais je voudrais savoir s'il existe une maniere mathematique pour prouver que la complexite d'un algorithme est logarithmique ou exponentielle.
merci

[FrancisSourd]

Il n'y a pas une manière type pour obtenir de tels preuves. Pour le log(n), le mieux est de regarder la preuve de l'insertion dans un tas: un arbre équilibré de n noeuds à une profondeur en O(log n). Les complexité en log n provient souvent de cette propriété.

La recherche dichotomique a aussi une complexité en O(log n). La structure d'arbre n'est pas explicite mais on la retrouve sans difficulté (cf ce que dit Toto13).

Pour les complexités exponentielles, les raisonnements combinatoires sont souvent la clé (énumération de toutes les permutations, de toutes les partitions...) Là encore, l'arbre est utile: ces énumérations se font souvent à l'aide d'un arbre d'énumération de profondeur n (ou n^2) qui ont ainsi un nombre exponentiels de nœuds.

[ToTo13]

Bonjour,

dans le cas du QuickSort, un lourd calcul de proba montre que la complexité est en O(N Log N).
Donc la réponse à ta question est très certainement oui, mais je ne connais pas la méthode.

[pseudocode]

merci pour votre reponse mais je voudrais savoir s'il existe une maniere mathematique pour prouver que la complexite d'un algorithme est logarithmique ou exponentielle.
merci

Oui, bien sur. La complexité est une mesure mathématique à la base.

On commence par ecrire la fonction de complexité telle qu'elle apparait dans l'algorithme. Généralement Cette fonction dépend à la fois du "rang" (= numero d'iteration / profondeur de recursion) et de la complexité pour les rangs suivants/prédédants. Le but est de ré-ecrire cette fonction pour qu'elle dépende uniquement des donnés de départ (taille, longueur, ...)

Par exemple, la recherche dichotomique sépare une liste en 2 puis explore l'une des deux parties. Donc pour une liste de taille N, la complexité est de:

Code :

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

1
2
3
4
5
6
 
C(N) = 1 + C(N/2)
       |     |
       |     Exploration d'une des 2 listes
       |  
     1 operation de separation

Maintenant, un peu de mathématiques

C(N) = 1 + C(N/2)

Changement de variables: N=2^t

C(2^t) = 1 + C (2^t/2) = 1 + C (2^(t-1))

Par récursion, on obtient:

C(2^t) = C(2^(t-1)) +1 = C(2^(t-2)) +1 +1 = ... = C(2^0) + t = Constante + t

donc l'algo est en O(t).

Et, par changement de variable inverse:

O(t) = O(log n / log 2) = O(log n)

CQFD

[Rniamo]

je crois que tu peux le trouver apr quelques théorème d'encadrements si tu as une relation de récurrence entre le rang n et n-1 mais je ne vois pas comment faire si ton programme est linéaire (et je doute qu'il soit autre chose que polynomial si tel est le cas).

[an1981]

bjr, pour le cas lineaire moi aussi je crois que c'est polynomial. le probleme est : dans le cas où l'algorithme est exponentiel (ou logarithmique), je ne sais pas !, mais je cois qu'on ne peut pas trouiver l'expression de la complexité explicitement. Et on peut uniquement affirmer qu'il est exponentiel en l'analysant.

Contrairement au cas polynoimal où on peut trouver l'expression de cette complexité (par exemple C(n) = 3n^2+2n+1).

moi ce que je veux c'est plutot le premier cas (exponentiel ou logarithmique) car pour le cas polynomial c'est bon je sais le faire.

merci