Existe-t-il une liste maîtresse de la notation Big-O pour tout?
https://stackoverflow.com/questions/180510
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Existe-t-il une liste maîtresse de la notation Big-O pour tout? Structures de données, algorithmes, opérations effectuées sur chacun, cas moyen, cas le plus défavorable, etc.
La solution
dictionnaire des algorithmes et des structures de données est une liste assez complète, avec une complexité O) dans les descriptions des algorithmes. Si vous avez besoin de plus d’informations, c’est dans l’une des références référencées. Il y a toujours une solution de rechange pour Wikipedia.
Autres conseils
Le livre Cormen a pour objectif de vous apprendre à prouver ce qu'est Big. -O serait pour un algorithme donné, plutôt que la mémorisation par cœur de l'algorithme à sa performance Big-O. Le premier est beaucoup plus précieux que le dernier et nécessite un investissement de votre part.
Essayez de " Introduction aux algorithmes " par Cormen, Leisersen et Rivest. Si ce n’est pas là, ce n’est probablement pas la peine de le savoir.
En c ++, les normes STL sont définies par les caractéristiques Big-O des algorithmes ainsi que par les besoins en espace. De cette façon, vous pouvez passer d'une implémentation STL concurrente à une autre et savoir que votre programme a les mêmes caractéristiques d'exécution. Des implémentations STL particulièrement bonnes pourraient même que les listes de cas particuliers de types particuliers soient meilleures que les exigences standard.
Il était facile de choisir le type d'itérateur ou de liste approprié à un problème particulier, car vous pouviez facilement peser entre la consommation d'espace et la vitesse.
Bien sûr, Big-O n’est qu’une ligne de repère car toutes les constantes sont supprimées. Si un algorithme fonctionne dans k * O (n), il serait classé comme O (n), mais si k est suffisamment élevé, il pourrait être pire que O (n ^ 2) pour certaines valeurs de n et m.
Introduction aux algorithmes, Deuxième édition , également appelé CLRS (Cormen, Leiserson, Rivest, Stein) , est la chose la plus proche que je puisse penser.
Si cela échoue, essayez alors l'art de la programmation informatique , par Knuth. Si ce n’est pas le cas, vous devrez probablement effectuer de véritables recherches.
À quiconque s’intéresse à cette question de Google.
