Bonjour :D,
comment représenter graphiquement tous les complexités
des algorithmes ?
O(p(n))?
:P
merci
Version imprimable
Bonjour :D,
comment représenter graphiquement tous les complexités
des algorithmes ?
O(p(n))?
:P
merci
merci d'utiliser la fonction
:recherch:
http://algo.developpez.com/faq/?page=complexe
merci pour la réponse
:P
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 !
Je ne sais pas
bonne remarque. Une erreur de retranscription en HTML...Citation:
Envoyé par alex_pi
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
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 !