Looking for big-o Keywords? Try Ask4Keywords

big-oErste Schritte mit Big-O


Bemerkungen

In diesem Abschnitt erhalten Sie einen Überblick darüber, was Big-O ist und warum ein Entwickler es möglicherweise verwenden möchte.

Es sollte auch alle großen Themen in Big-O erwähnen und auf die verwandten Themen verweisen. Da die Dokumentation für big-o neu ist, müssen Sie möglicherweise erste Versionen dieser verwandten Themen erstellen.

Berechnung von Big-O für Ihren Code

Eine Möglichkeit, den Big-O-Wert einer von Ihnen geschriebenen Prozedur zu berechnen, besteht darin, zu bestimmen, welche Codezeile angesichts Ihrer Eingabegröße n in Ihrer Funktion am häufigsten ausgeführt wird. Wenn Sie diese Zahl haben, nehmen Sie alle außer den am schnellsten wachsenden Ausdrücken heraus und entfernen Sie die Koeffizienten - das ist die Big-O-Notation Ihrer Funktion.

In dieser Funktion wird beispielsweise jede Zeile genau einmal und für die gleiche Zeit ausgeführt, unabhängig davon, wie groß a ist:

int first(int[] a){
   printf("Returning the first element of a");
   return a[0];
}
 

Die Funktion selbst kann 1 Millisekunde ((1 ms) * n 0 ) oder 100 Millisekunden ((100 ms) * n 0 ) dauern. Der genaue Wert hängt von der Leistung des Computers ab und davon, an was printf() gedruckt wird. Da sich diese Faktoren jedoch nicht mit der Größe von a ändern, spielen sie bei Big-O-Berechnungen keine Rolle. Sie sind konstante Koeffizienten, die wir entfernen. Daher hat diese Funktion einen Big-O-Wert von O (1) .

In dieser Funktion wird Zeile 3 ( sum += a[i]; ) einmal für jedes Element in a , insgesamt also a.length (oder n ) mal:

int sum(int[] a){
   int sum = 0;
   for (int i = 0; i < a.length; i++){
        sum += a[i];
   }
   return sum;
}
 

Die Anweisungen i++ und i < a.length jeweils auch n- mal ausgeführt - wir hätten diese Zeilen i < a.length können, müssen aber nicht. int sum = 0; , int i = 0 und return sum; Jeder Lauf einmal, was weniger als n Mal ist - wir ignorieren diese Zeilen. Es spielt keine Rolle, wie lange die sum += a[i] dauert - dies ist ein Koeffizient, der von der Leistung des Computers abhängt - daher entfernen wir diesen Koeffizienten. Daher ist diese Funktion O (n) .

Wenn mehrere Codepfade vorhanden sind, wird big-O normalerweise aus dem ungünstigsten Fall berechnet. Obwohl diese Funktion möglicherweise sofort beendet werden kann, unabhängig davon, wie groß a ist (wenn a[0] 0 ), existiert immer noch ein Fall, in dem Zeile 6 mal a.length wird. Es ist also immer noch O (n):

int product(int[] a){
    int product = 0;
    for (int i = 0; i < a.length; i++){
        if (a[i] == 0)
            return 0;
        else 
            product *= a[i];
    }
    return product;
}
 

Was ist Big-O-Notation?

Die Big-O-Notation ist eine Notation, mit der über die langfristigen Wachstumsraten von Funktionen gesprochen wird. Es wird häufig bei der Analyse von Algorithmen verwendet, um über die Laufzeit eines Algorithmus oder verwandte Konzepte wie Raumkomplexität zu sprechen.

Im allgemeinen Sprachgebrauch wird die Big-O-Notation verwendet, um darüber zu sprechen, wie die Laufzeit eines Algorithmus als Größe der Eingabe skaliert. Wir würden beispielsweise sagen, dass die Auswahlsortierung eine Laufzeit von O (n 2 ) hat, da die Laufzeit quadratisch als Funktion der Größe des zu sortierenden Arrays wächst. Das heißt, wenn Sie die Größe der Eingabe verdoppeln, sollte sich die Laufzeit der Auswahlsortierung ungefähr verdoppeln. Bei Verwendung der Big-O-Notation besteht die Konvention darin, Koeffizienten zu löschen und niederwertige Terme zu ignorieren. Während es technisch gesehen nicht falsch ist, zu sagen, dass die binäre Suche in der Zeit O (2 log 2 n + 17) ausgeführt wird, gilt dies als schlechter Stil, und es ist besser zu schreiben, dass die binäre Suche in der Zeit O (log n) ausgeführt wird.

Formal wird die Big-O-Notation verwendet, um das Langzeitverhalten einer Funktion zu quantifizieren. Wir sagen, dass f (n) = O (g) (manchmal in einigen Quellen mit f (n) ∈ O (g (n)) bezeichnet), wenn es feste Konstanten c und n 0 gibt, so dass f (n) ≤ c · g ist (n) für alle n ≥ n 0 . Diese formale Definition erklärt, warum wir uns nicht um niederwertige Termini kümmern (sie können durch Erhöhen von c und Erhöhen von n 0 subsumiert werden) und konstante Faktoren (der c-Term absorbiert sie). Diese formale Definition wird häufig in der rigorosen Analyse von Algorithmen verwendet, wird jedoch selten umgangssprachlich verwendet.