Ist dies eine richtige „Regel“ zum Identifizieren der „Big O“ -Notation eines Algorithmus?

Ich habe mehr über die Big O-Notation gelernt und wie man sie berechnet, basierend darauf, wie ein Algorithmus geschrieben ist. Ich bin auf einen interessanten Satz von "Regeln" zur Berechnung einer Algorithmus-Big-O-Notation gestoßen und wollte sehen, ob ich auf dem richtigen Weg bin oder nicht.

Big O-Notation: N

function(n) {
    For(var a = 0; i <= n; i++) { // It's N because it's just a single loop
        // Do stuff
    }
}

Big O-Notation: N ²

function(n, b) {
    For(var a = 0; a <= n; a++) {
        For(var c = 0; i <= b; c++) { // It's N squared because it's two nested loops
            // Do stuff
        }
    }
}

Big O-Notation: 2N

function(n, b) {
    For(var a = 0; a <= n; a++) {
        // Do stuff
    }
    For(var c = 0; i <= b; c++) { // It's 2N the loops are outside each other
        // Do stuff
    }
}

Big O-Notation: NLogN

function(n) {
    n.sort(); // The NLogN comes from the sort?
    For(var a = 0; i <= n; i++) {
        // Do stuff
    }
}

Sind meine Beispiele und die nachfolgende Notation korrekt? Gibt es zusätzliche Notizen, auf die ich achten sollte?

Formal beschreibt die Big-O-Notation den Grad der Komplexität.

So berechnen Sie die Big-O-Notation:

1. Identifizieren Sie die Formel für die Komplexität des Algorithmus. Nehmen wir zum Beispiel zwei Schleifen an, in denen eine weitere geschachtelt ist, und dann drei weitere Schleifen, die nicht geschachtelt sind:2N² + 3N
2. alles außer dem höchsten Begriff entfernen: 2N²
3. entferne alle Konstanten: N²

Mit anderen Worten, zwei Schleifen, in denen eine weitere verschachtelt ist, und drei weitere, nicht verschachtelte Schleifen, sind O (N²).

Dies setzt natürlich voraus, dass das, was Sie in Ihren Schleifen haben, einfache Anweisungen sind. Wenn Sie sich zum Beispiel sort()innerhalb der Schleife befinden, müssen Sie die Komplexität der Schleife mit der Komplexität der sort()Implementierung multiplizieren, die Ihre zugrunde liegende Sprache / Bibliothek verwendet.

Wenn Sie diese Algorithmen analysieren möchten, müssen Sie // Dostuff definieren, da dies das Ergebnis wirklich ändern kann. Nehmen wir an, Dostuff erfordert eine konstante Anzahl von O (1) Operationen.

Hier sind einige Beispiele mit dieser neuen Notation:

Für Ihr erstes Beispiel, das lineare Verfahren: Das ist richtig!

AUF):

for (int i = 0; i < myArray.length; i++) {
    myArray[i] += 1;
}

Warum ist es linear (O (n))? Wenn wir dem Eingang (Array) zusätzliche Elemente hinzufügen, nimmt die Anzahl der Operationen proportional zur Anzahl der hinzugefügten Elemente zu.

Wenn also eine Operation erforderlich ist, um eine Ganzzahl irgendwo im Speicher zu erhöhen, können wir die Arbeit der Schleife mit f (x) = 5x = 5 zusätzlichen Operationen modellieren. Für 20 zusätzliche Elemente führen wir 20 zusätzliche Operationen durch. Ein einzelner Durchgang eines Arrays ist in der Regel linear. Dies gilt auch für Algorithmen wie Bucket Sort, die die Datenstruktur ausnutzen können, um eine Sortierung in einem einzigen Durchgang eines Arrays durchzuführen.

Ihr zweites Beispiel wäre ebenfalls korrekt und sieht folgendermaßen aus:

O (N ^ 2):

for (int i = 0; i < myArray.length; i++) {
    for (int j = 0; j < myArray.length; j++) {
        myArray[i][j] += 1;
    }
}

In diesem Fall müssen wir für jedes zusätzliche Element im ersten Array i ALLES von j verarbeiten. Durch Hinzufügen von 1 zu i wird j tatsächlich hinzugefügt (Länge von j). Sie haben also Recht! Dieses Muster ist O (n ^ 2), oder in unserem Beispiel ist es tatsächlich O (i * j) (oder n ^ 2, wenn i == j, was häufig bei Matrixoperationen oder einer quadratischen Datenstruktur der Fall ist.

Ihr drittes Beispiel ist, wo sich die Dinge in Abhängigkeit von Dostuff ändern. Wenn der Code wie geschrieben ist und do stuff eine Konstante ist, ist es eigentlich nur O (n), weil wir 2 Durchgänge eines Arrays der Größe n haben und 2n auf n reduziert wird. Die Schleifen, die außerhalb voneinander liegen, sind nicht der Schlüsselfaktor, der 2 ^ n-Code erzeugen kann. Hier ist ein Beispiel für eine Funktion, die 2 ^ n ist:

var fibonacci = function (n) {
    if (n == 1 || n == 2) {
        return 1;
    }

    else {
        return (fibonacci(n-2) + fibonacci(n-1));
    }
}

Diese Funktion ist 2 ^ n, da jeder Aufruf der Funktion ZWEI zusätzliche Aufrufe der Funktion (Fibonacci) erzeugt. Mit jedem Aufruf der Funktion verdoppelt sich der Arbeitsaufwand! Das wächst super schnell, als würde man einer Hydra den Kopf abschneiden und jedes Mal zwei neue sprießen lassen!

Wenn Sie für Ihr letztes Beispiel eine nlgn-Sortierung wie "Merge-Sort" verwenden, haben Sie Recht, dass dieser Code O (nlgn) lautet. Sie können jedoch die Struktur der Daten ausnutzen, um in bestimmten Situationen schnellere Sortierungen zu entwickeln (z. B. über einen bekannten, begrenzten Wertebereich von 1 bis 100). Wenn also eine O (nlgn) -Sorte neben einer Operation steht, die weniger als O (nlgn) Zeit benötigt, ist die Gesamtzeitkomplexität O (nlgn).

In JavaScript (zumindest in Firefox) lautet die Standardsortierung in Array.prototype.sort () in der Tat MergeSort. Sie suchen also bei O (nlgn) nach Ihrem endgültigen Szenario.

Ihr zweites Beispiel (äußere Schleife von 0 bis n , innere Schleife von 0 bis b ) wäre O ( nb ), nicht O ( n ² ). Die Regel ist, dass Sie n- mal etwas berechnen , und für jeden von denen Sie b- mal etwas anderes berechnen , daher hängt das Wachstum dieser Funktion nur vom Wachstum von n * b ab .

Ihr drittes Beispiel ist nur O ( n ) - Sie können alle Konstanten entfernen, da sie nicht mit n wachsen und es sich bei der Big-O-Notation um Wachstum handelt.

Was Ihr letztes Beispiel betrifft, ja, Ihre Big-O-Notation wird sicherlich von der Sortiermethode stammen, die, wenn sie vergleichsbasiert ist (wie es normalerweise der Fall ist), in ihrer effizientesten Form O ( n * logn ) ist. .

Denken Sie daran, dass dies eine ungefähre Darstellung der Laufzeit ist. Die "Faustregel" ist ungefähr, weil sie ungenau ist, aber zu Bewertungszwecken eine gute Annäherung erster Ordnung liefert.

Die tatsächliche Laufzeit hängt davon ab, wie viel Heap-Speicherplatz, wie schnell der Prozessor, der Befehlssatz, die Verwendung von Präfix- oder Post-Fix-Inkrement-Operatoren usw. zur Verfügung stehen. Durch eine ordnungsgemäße Laufzeitanalyse kann die Akzeptanz bestimmt werden. Wenn Sie jedoch die Grundlagen kennen, können Sie von Anfang an programmieren.

Ich stimme Ihnen zu, dass Sie auf dem richtigen Weg sind, um zu verstehen, wie Big-O von einem Lehrbuch zu einer praktischen Anwendung rationalisiert wird. Das könnte die schwierige Hürde sein, die es zu überwinden gilt.

Die asymptotische Wachstumsrate wird bei großen Datenmengen und großen Programmen wichtig, sodass Sie anhand typischer Beispiele zeigen, dass es für die richtige Syntax und Logik nicht so wichtig ist.

Big oh, per Definition bedeutet: Für eine Funktion f (t) existiert eine Funktion c * g (t), wobei c eine beliebige Konstante ist, so dass f (t) <= c * g (t) für t> n ist, wobei n ist eine beliebige Konstante, dann existiert f (t) in O (g (t)). Dies ist eine mathematische Notation, die in der Informatik zur Analyse von Algorithmen verwendet wird. Wenn Sie verwirrt sind, würde ich empfehlen, sich mit den Abschlussbeziehungen zu befassen. Auf diese Weise können Sie in einer detaillierteren Ansicht sehen, wie diese Algorithmen diese Big-Oh-Werte erhalten.

Einige Konsequenzen dieser Definition: O (n) ist tatsächlich kongruent zu O (2n).

Es gibt auch viele verschiedene Arten von Sortieralgorithmen. Der kleinste Big-Oh-Wert für eine Vergleichssorte ist O (nlogn), es gibt jedoch viele Sorten mit schlechterem Big-Oh. Zum Beispiel hat die Auswahlsortierung O (n ^ 2). Einige nicht vergleichbare Sorten haben möglicherweise bessere Big-Oh-Werte. Eine Bucket-Sortierung hat beispielsweise O (n).