Discussion :

[Black.Rose]

Bonjour ,
comment représenter graphiquement tous les complexités
des algorithmes ?
O(p(n))?

merci

[souviron34]

merci d'utiliser la fonction



http://algo.developpez.com/faq/?page=complexe

[Black.Rose]

merci pour la réponse

[alex_pi]

D'ailleurs il va falloir faire quelque chose à cette FAQ, elle est complètement fausse . Rien que la définition de la notation O est à l'envers !

[Black.Rose]

Je ne sais pas

[pseudocode]

D'ailleurs il va falloir faire quelque chose à cette FAQ, elle est complètement fausse . Rien que la définition de la notation O est à l'envers !

bonne remarque. Une erreur de retranscription en HTML...

[FR119492]

Bonjour à tous!
Au risque de choquer certains d'entre vous, je tiens à exprimer mon scepticisme à l'égard de l'utilisation concrète de la notion de complexité pour le choix d'une méthode de calcul numérique: pour l'inversion d'une matrice, l'algorithme LU a une complexité de 3, celui de Strassen de 2,807 et celui de Coppersmith et Winograd de 2,376. Or qui utilise ces deux derniers?
Jean-Marc Blanc

[alex_pi]

Qui a parlé de méthode de calcul numérique ? Et ensuite, quand les exposants sont proches, il faut regarder la constante ainsi que les termes négligeables pour voir à partir de quel n ça vaut le coup. Et enfin, évidement, il faut tenir compte de la difficulté de l'algo !

En revanche, un tri à bulle est en n^2, un tri rapide (en moyenne) en n ln(n). Qui utilise le premier ? Personne Qu'est ce qui te dit qu'un arbre binaire équilibré est mieux qu'un tableau en vrac quand tu cherches un élément ? Un complexité logarithmique dans un cas, linéaire dans l'autre.

Évidemment la complexité ne saurait être le seul facteur de choix. Mais s'en est un important !