Was ist Big O-Zeitkomplexität?

Die in diesem Blog verfassten Artikel wurden mit dem Ziel erstellt, zu unterrichten. Außerdem können die Informationen im Artikel falsch sein, also seien Sie bitte vorsichtig.

Die Big-O-Notation drückt aus, mit welcher Geschwindigkeit der Rechenaufwand mit zunehmender Eingabegröße zunimmt. Der Zweck unterscheidet sich von einem Benchmark, der genau angibt, wie viele Nanosekunden es dauert.

Häufig beobachtete Komplexität

O(1)-Array-Indexzugriff
O(log N) binäre Suche
O(N) vollständige Durchquerung
O(N log N) allgemeine Vergleichssortierung
O(N²) vergleiche alle Paare

Konstanten werden weggelassen

for (int Value : Values)
{
    ProcessA(Value);
}

for (int Value : Values)
{
    ProcessB(Value);
}

Da es zweimal durchlaufen wird, ist die eigentliche Operation2NIn der Nähe von , aber in Big OO(N)Drücken Sie es aus als Dies liegt daran, dass der Schwerpunkt auf der zunehmenden Ordnung liegt, wenn N wächst.

Das Ignorieren von Konstanten bedeutet nicht, dass sie für die tatsächliche Leistung nicht wichtig sind. Cache-freundlichO(N)Wenn Ihr Code bei komplexen Konstanten anders istO(N)Es kann viel schneller sein als Code.

am schlechtesten, durchschnittlich, am besten

Die lineare Suche findet das erste ElementO(1), aber wenn es fehlt oder am EndeO(N)Bin. Wenn Sie nicht aufschreiben, um welchen Fall es sich handelt, wird derselbe Algorithmus anders erklärt.

Big O ist der erste Filter zur Auswahl eines Algorithmus. Die endgültige Wahl sollte gegen die tatsächliche Datengröße, Speichernutzung, Cache und Implementierungskomplexität abgewogen werden.