Gibt es eine Master-Liste der Big-O-Notation für alles?
https://stackoverflow.com/questions/180510
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Gibt es eine Master-Liste der Big-O-Notation für alles? Datenstrukturen, Algorithmen, Operationen an jedem durchgeführt, durchschnittlichen Fall, Worst-Case-etc.
Lösung
Wörterbuch von Algorithmen und Datenstrukturen eine ziemlich umfassende Liste ist, und umfasst Komplexität (Big- O) in den Bezeichnungen Algorithmen. Wenn Sie weitere Informationen benötigen, wird es in einem der verknüpften Referenzen sein, und es gibt immer Wikipedia als Ausweich.
Andere Tipps
Das Cormen Buch ist, mehr über Sie zu lehren, wie zu beweisen, was Big -O würde für einen bestimmten Algorithmus, anstatt Auswendiglernen des Algorithmus auf seine Big-O-Performance. Ersteres ist viel wertvoller als die letztere, und erfordert eine Investition von Ihrer Seite.
Versuchen " Introduction to Algorithms " von Cormen, Leisersen und Rivest . Wenn es da nicht sein wahrscheinlich nicht wert zu kennen.
In c ++ die STL-Standards wird durch die Big-O Eigenschaften der Algorithmen sowie den Platzbedarf definiert. So können Sie zwischen konkurrierenden Implementierungen von STL wechseln konnte und wissen noch, dass Ihr Programm die gleichen ish Laufzeiteigenschaften hatte. Particularily gute STL-Implementierungen könnten sogar Sonderfall Listen von bestimmten Arten besser sein als die Standard-Anforderungen.
Es machte es leicht, den richtigen Iterator oder Listentyp für ein bestimmtes Problem zu holen, weil Sie einfach zwischen Platzverbrauch und Geschwindigkeit wiegen könnten.
Ofcourse Big-O ist nur eine Führungslinie als alle Konstanten entfernt werden. Wenn ein Algorithmus in k * O läuft (n), wäre es als O eingestuft werden (n), aber wenn k ausreichend hoch ist, könnte es sein, schlimmer als O (n ^ 2) für einige Werte von n und m.
Introduction to Algorithms, Second Edition , auch bekannt als CLRS (Cormen, Leiserson, Rivest, Stein) ist das nächste, was ich mir vorstellen kann.
Wenn das nicht funktioniert, dann versuchen The Art of Computer Programming von Knuth. Wenn es nicht in jene ist, müssen Sie wahrscheinlich einige echte Forschung tun.
Für jeden, der auf diese Frage von Google kommt.
