Gibt es eine Master-Liste der Big-O-Notation für alles? Datenstrukturen, Algorithmen, Operationen, die an jedem, Durchschnittsfall, Worst-Case usw. durchgeführt werden.Gibt es eine Master-Liste der Big-O-Notation für alles?
Dictionary of Algorithms and Data Structures ist eine ziemlich umfassende Liste und enthält Komplexität (Big-O) in den Beschreibungen der Algorithmen. Wenn Sie mehr Informationen benötigen, wird es in einer der verknüpften Referenzen sein, und es gibt immer Wikipedia als Fallback.
Versuchen Sie "Introduction to Algorithms" von Cormen, Leisersen und Rivest. Wenn es nicht drin ist, ist es wahrscheinlich nicht wissenswert.
Introduction to Algorithms, Second Edition, auch bekannt als CLRS (Cormen, Leiserson, Rivest, Stein), ist das nächste, was ich mir vorstellen kann.
Wenn das fehlschlägt, versuchen Sie The Art of Computer Programming, von Knuth. Wenn es nicht in denen ist, müssen Sie wahrscheinlich wirklich recherchieren.
Die Cormen book ist mehr über Lehre, wie man beweist, was Big-O für einen bestimmten Algorithmus wäre, anstatt das Auswendiglernen des Algorithmus für seine Big-O-Leistung. Ersteres ist viel wertvoller als das Letztere und erfordert eine Investition von Ihrer Seite.
In C++ sind die STL-Standards durch die Big-O-Eigenschaften der Algorithmen sowie die Platzanforderungen definiert. Auf diese Weise können Sie zwischen konkurrierenden Implementierungen von STL wechseln und wissen, dass Ihr Programm die gleichen Laufzeiteigenschaften hat. Besonders gute STL-Implementierungen könnten sogar Sonderfalllisten bestimmter Typen besser als die Standardanforderungen sein.
Es machte es einfach, den richtigen Iterator oder Listentyp für ein bestimmtes Problem auszuwählen, weil Sie leicht zwischen Speicherplatzverbrauch und Geschwindigkeit abwägen konnten.
Natürlich ist Big-O nur eine Hilfslinie, da alle Konstanten entfernt sind. Wenn ein Algorithmus in k * O (n) läuft, würde er als O (n) klassifiziert werden, aber wenn k ausreichend hoch ist, könnte er für einige Werte von n und m schlechter als O (n^2) sein.
Für jeden, der auf diese Frage von Google kommt.
ich heruntergeladen alle Seiten und machte eine Liste jeder Seite aus, die großen o bietet: https://pastebin.com/X3c7i4aF – BlackCap