Was ist Big O-Notation? Benutzt du es? [Duplikat]

StackOverflow https://stackoverflow.com/questions/133008

War es hilfreich?

Lösung

Eine wichtige Sache, die meisten Leute vergessen, wenn es um Big-O sprechen, so habe ich das Bedürfnis, das zu erwähnen:

Sie können keine Big-O verwenden Sie die Geschwindigkeit von zwei Algorithmen zu vergleichen. Big-O sagt nur, wie viel langsamer wird ein Algorithmus erhalten (ungefähr), wenn Sie die Anzahl der Elemente verarbeitet verdoppeln, oder wie viel schneller es wird, wenn man die Zahl halbiert.

Wenn Sie jedoch zwei völlig unterschiedliche Algorithmen und eine (A) ist O(n^2) und der andere (B) O(log n) wird, ist es nicht gesagt, dass A langsamer als B ist. Eigentlich mit 100 Stück, A vielleicht zehnmal schneller als B sein. Es sagt nur, dass mit 200 Stück, A um den Faktor n^2 langsamer wachsen wird und B wird um den Faktor log n langsamer wachsen. Also, wenn Sie Benchmark beide, und Sie wissen, wie viel Zeit A nimmt 100 Elemente zu verarbeiten, und wie viel Zeit B benötigt für die gleiche Stückzahl von 100, und A ist schneller als B, können Sie in welcher Höhe der Elemente berechnen B A überholen in Geschwindigkeit (wie die Geschwindigkeit des B als die von A viel langsamer abnimmt, wird es A früher überholt oder später, das ist sicher).

Andere Tipps

Big O-Notation bezeichnet den limitierenden Faktor eines Algorithmus. Es ist ein vereinfachte Ausdruck, wie die Laufzeit einer Algorithmus Waage mit Bezug auf den Eingang.

Zum Beispiel (in Java): 

/** Takes an array of strings and concatenates them
  * This is a silly way of doing things but it gets the 
  * point across hopefully
  * @param strings the array of strings to concatenate
  * @returns a string that is a result of the concatenation of all the strings
  *          in the array
  */
public static String badConcat(String[] Strings){
    String totalString = "";
    for(String s : strings) {
        for(int i = 0; i < s.length(); i++){
            totalString += s.charAt(i);
        }
    }
    return totalString;
}

Jetzt darüber nachdenken, was dies tatsächlich tun. Es wird durch jedes Zeichen der Eingabe und das Hinzufügen von ihnen zusammen. Dies scheint einfach. Das Problem ist, dass String ist unveränderlich . Also jedes Mal, wenn Sie einen Brief auf die Saite hinzufügen müssen Sie einen neuen String erstellen. Um dies zu tun, müssen Sie die Werte aus der alten Zeichenfolge in die neue Zeichenfolge kopieren und fügen Sie den neuen Charakter.

Dies bedeutet, dass Sie die ersten Buchstaben werden Kopieren n Zeiten, in denen n ist die Anzahl der Zeichen in der Eingabe. Sie werden die Zeichen n-1 Zeiten werden kopiert, so insgesamt wird es (n-1)(n/2) Kopien sein.

Dies ist (n^2-n)/2 und für Big O-Notation verwenden wir nur den höchsten Wert Faktor (in der Regel) und alle Konstanten fallen, die durch sie multipliziert werden und wir am Ende mit O(n^2).

so etwas wie ein StringBuilder Verwendung entlang der Linien von O sein (nMelden (n)). Wenn Sie die Anzahl der Zeichen am Anfang berechnen und stellen Sie die Kapazität des StringBuilder können Sie es O(n) werden.

Wenn wir also 1000 Zeichen von Eingabe haben, das erste Beispiel etwa eine Million Operationen durchführen würde, würde StringBuilder 10.000 durchführen und die StringBuilder mit setCapacity durchführen würden 1000 Operationen, das Gleiche zu tun. Das ist grobe Schätzung, aber O(n) Notation ist über Größenordnung, nicht genaue Laufzeit.

Es ist nicht etwas, das ich pro sagen auf einer regelmäßigen Basis. Es ist jedoch ständig im Hinterkopf, wenn sie versucht, etwas zu tun den besten Algorithmus, um herauszufinden.

Eine sehr ähnliche Frage bereits unter Big-O für acht Jährige gefragt worden? . Hoffentlich werden die Antworten wird es Ihre Frage zu beantworten, obwohl die Frage Fragesteller hat es hatte ein wenig mathematisches Wissen über alles, die Sie vielleicht nicht so klären, ob Sie eine ausführlichere Erklärung benötigen.

sollte Jeder Programmierer bewusst sein, was Big O-Notation ist, wie sie für Maßnahmen mit gemeinsamen Datenstrukturen und Algorithmen gilt (und damit die richtigen DS und Algorithmus für das Problem holen sie zu lösen), und wie es berechnen für ihre eigene Algorithmen.

1) Es ist eine Ordnung der Messung der Effizienz eines Algorithmus, wenn sie auf einer Datenstruktur arbeiten.

2) Aktionen wie ‚add‘ / ‚sortiert‘ / ‚entfernen‘ unterschiedliche Mengen an Zeit in Anspruch nehmen kann mit unterschiedlichen Datenstrukturen (und Algorithmen) zum Beispiel ‚add‘ und ‚finden‘ sind O (1) für ein hashmap , aber O (log n) für einen binären Baum. Sort ist O (n log n) für QuickSort, aber O (n ^ 2) für BubbleSort, wenn sie mit einem einfachen Array handelt.

3) Berechnungen können durch einen Blick auf die Schleife Tiefe des Algorithmus im Allgemeinen durchgeführt werden. Keine Schleifen, O (1), Loops Iterieren über die ganzen Satz O (n) (auch wenn sie irgendwann ausbrechen). Wenn die Schleifenhälften auf jeder Iteration den Suchraum? O (log n). Nehmen Sie die höchste O () für eine Folge von Schleifen und multiplizieren Sie die O (), wenn Sie nisten Schleifen.

Ja, es ist komplizierter als das. Wenn Sie wirklich daran interessiert sind, ein Lehrbuch bekommen.

‚Big-O‘ Schreibweise verwendet wird, um die Wachstumsraten von zwei Funktionen einer Variablen vergleichen (sagen n) als n sehr groß wird. Wenn die Funktion f viel schneller als Funktion g wächst sagen wir, dass g = O (f), die für groß genug, um n zu implizieren, f wird immer größer als g bis zu einem Skalierungsfaktor.

Es stellt sich heraus, dass dies eine sehr nützliche Idee in der Informatik und insbesondere bei der Analyse von Algorithmen, weil wir mit den Wachstumsraten von Funktionen oft genau betroffen sind, die zum Beispiel darstellen, die durch zwei verschiedene Algorithmen Zeit genommen. Sehr grob, können wir feststellen, dass der, wenn t1 effizienter ist ein Algorithmus mit Laufzeit t1 (n) als ein Algorithmus mit Laufzeit t2 (n) = O (t2) für groß genug, um n die in der Regel ist die ‚Größe‘ das Problem -. wie die Länge des Arrays oder die Anzahl der Knoten in der Grafik oder was auch immer

Diese Bestimmung, dass n groß genug wird, ermöglicht es uns, eine Menge nützlicher Tricks zu ziehen. Vielleicht ist die am häufigsten verwendete ist, dass Sie Funktionen bis auf die am schnellsten wachsenden Begriffe vereinfachen kann. Zum Beispiel n ^ 2 + n = O (n ^ 2), weil, wie n groß genug wird, die n ^ 2 Begriff bekommt so viel größer als n, die der n Begriff praktisch unbedeutend ist. So können wir es aus der Betrachtung fallen.

Doch es bedeutet, dass Big-O-Notation für klein n weniger nützlich, weil die langsamen wachsenden Bedingungen, die wir über noch signifikant genug sind, vergessen haben, die Laufzeit zu beeinflussen.

Was wir jetzt haben, ist ein Werkzeug für die Kosten von zwei verschiedenen Algorithmen zu vergleichen und eine Abkürzung zu sagen, dass man schneller oder langsamer als die andere ist. Big-O-Notation kann dazu missbraucht werden, was eine Schande ist, da es ungenau schon genug ist! Es gibt äquivalente Begriffe zu sagen, dass eine Funktion als eine anderen weniger schnell wächst, und dass zwei Funktionen wachsen mit der gleichen Rate.

Oh, und verwende ich es? Ja, die ganze Zeit - wenn ich herauszufinden, wie effizient mein Code ist es gibt eine große ‚Back-of-the-Briefumschlag- Annäherung an den Kosten.

Die "Intuitition" hinter Big-O

Stellen Sie sich einen "Wettbewerb" zwischen zwei Funktionen über x, wenn x gegen unendlich. F (x) und g (x)

Wenn nun von einem Punkt auf (ein x) eine Funktion immer einen höheren Wert hat dann die andere, dann lassen Sie uns diese Funktion aufrufen „schneller“ als die andere.

So zum Beispiel, wenn für jeden x> 100 Sie sehen, dass f (x)> g (x), dann f (x) "schneller" als g (x).

In diesem Fall würden wir sagen, g (x) = O (f (x)). f (x) stellt eine Art „Geschwindigkeitsbegrenzung“ von Sorten für g (x), da schließlich geht es es und hinterlässt es für gut.

Dies ist nicht gerade die Definition von big-O-Notation , die auch besagt, dass f (x) nur größer als C * g (x) für eine konstante C (was ja nur eine andere Art und Weise ist, dass Sie es nicht g (x) gewinnen den Wettbewerb helfen können, um einen konstanten Faktor durch Multiplikation - f (x) wird immer am Ende gewinnen). Die formale Definition verwendet auch absolute Werte. Aber ich hoffe, dass ich es geschafft, es intuitiv zu machen.

Es kann auch eine Überlegung wert, dass die Komplexität vieler Algorithmen auf mehr als eine Variable basiert, insbesondere in mehrdimensionale Probleme. Zum Beispiel musste ich vor kurzem einen Algorithmus für die folgenden schreiben. Vorgegeben eine Menge von n Punkten ist, und m Polygonen, extrahieren alle Punkte, die in jedem der Polygone liegen. Die Komplexität basiert auf zwei bekannten Variablen, n und m, und das Unbekannte, wie viele Punkte in jedem Polygon sind. Die O-Notation hier ist ein bisschen mehr beteiligt als O (f (n)) oder auch O (f (n) + g (m)). Big O ist gut, wenn man mit einem großen Anzahl von homogenen Elementen zu tun hat, aber nicht erwarten, dass dies immer der Fall sein.

Es ist auch erwähnenswert, dass die tatsächliche Anzahl von Iterationen über die Daten oft auf den Daten abhängig ist. Quicksort ist in der Regel schnell, aber geben sie Daten vorsortiert und es verlangsamt. Meine Punkte und Polygone alogorithm recht schnell am Ende, in der Nähe O (n + (m log (m)), basierend auf Vorwissen, wie die Daten wahrscheinlich war organisiert und die relativen Größen von n und m werden. Es würde umfallen schlecht auf zufällig Daten von unterschiedlichen relativen Größen organisiert.

Eine letzte Sache zu prüfen ist, dass es oft ein direkter Handel zwischen der Geschwindigkeit eines Algorithmus und der Menge an Speicherplatz weg von ihm verwendet. Pigeon Loch Sortierung ist ein ziemlich gutes Beispiel dafür. zurück zu meiner Punkte und Polygone gehen, können sagen, dass alle meine Polygone einfach und schnell zu ziehen waren, und ich konnte sie auf dem Bildschirm gefüllt ziehen, sagen in blau, jeweils in einer festen Menge an Zeit. Also, wenn ich meinen m Polygone auf einem schwarzen Bildschirm ziehen würde es dauern, O (m) Zeit. Um zu überprüfen, ob jede meiner n Punkte in einem Polygon war, überprüfe ich einfach, ob das Pixel an diesem Punkt ist grün oder schwarz. So ist die Kontroll O (n), und die Gesamtanalyse ist O (m + n). Nachteil ist natürlich, dass ich in der Nähe von unendlich Speicher benötigen, wenn ich mit der realen Welt zu tun habe Koordinaten millimetergenau .... ... ho hum.

Es ist auch wert sein kann unter Berücksichtigung abgeschrieben Zeit, und nicht nur schlimmster Fall. Das bedeutet zum Beispiel, dass, wenn Sie den Algorithmus ausführen n Zeiten, wird es O (1) im Durchschnitt, aber es könnte schlimmer manchmal sein.

Ein gutes Beispiel ist eine dynamische Tabelle, die im Grunde ein Array ist, die, wie Sie erweitern Elemente hinzufügen. Eine naive Implementierung würde hinzugefügt, um die Anordnung der Größe von 1 für jedes Element erhöhen, was bedeutet, dass alle Elemente jedes Mal ein neuer hinzugefügt wird kopiert werden müssen. Dies würde zu einem O (n 2 ) Algorithmus, wenn Sie eine Reihe von Arrays wurden verketten mit dieser Methode. Eine Alternative ist die Kapazität des Arrays jedes Mal, wenn Sie brauchen mehr Speicher zu verdoppeln. Auch wenn Anfügen eine ist O (n) Betrieb manchmal, werden Sie nur kopieren müssen O (n) -Elemente für alle n Elemente hinzugefügt, so dass der Betrieb ist O (1) im Durchschnitt. Dies ist, wie Dinge wie String oder std :: vector umgesetzt werden.

Was ist Big O-Notation?

Big O-Notation ist ein Verfahren zur Bestimmung der Beziehung zwischen vielen Schritten zum Ausdruck wird ein Algorithmus auf die Größe der Eingangsdaten im Zusammenhang erfordern. Dies wird bezeichnet als die algorithmische Komplexität. Zum Beispiel eine Liste der Größe N Sortier Bubble Sort Verwendung nimmt O (N ^ 2) Schritte.

Muss ich Big O-Notation verwenden?

Ich benutze Big O-Notation gelegentlich algorithmische Komplexität zu Kollegen Programmierer zu vermitteln. Ich benutze die zugrunde liegende Theorie (zum Beispiel Big O Analysetechniken) alle von der Zeit, als ich darüber nachdenken, was Algorithmen zu verwenden.

Konkrete Beispiele?

Ich habe die Theorie der Komplexität Analyse verwendeten Algorithmen zur effizienten Stapeldatenstrukturen zu schaffen, die keine Erinnerung Neuzuteilung erfordern, und die Unterstützung durchschnittliche Zeit von O (N) für die Indizierung. Ich habe Big O-Notation verwendet, um den Algorithmus zu anderen Menschen zu erklären. Ich habe auch Komplexitätsanalyse zu verstehen, wenn die lineare Zeit Sortierung O (N) ist möglich verwendet.

Von Wikipedia .....

Big O-Notation ist nützlich, wenn Algorithmen für die Effizienz zu analysieren. Zum Beispiel nimmt die Zeit (oder die Anzahl der Schritte) ist es ein Problem der Größe n abzuschließen gefunden werden könnte T (n) = 4n² zu sein -. 2n + 2

Wie n groß wird, der n² Begriff wird kommen zu dominieren, so dass alle andere Bedingungen vernachlässigt werden können - zum Beispiel, wenn n = 500, der Begriff 4n² ist 1000-mal so groß wie der 2n Begriff. letztere Ignoriert für die meisten Zwecke würde eine vernachlässigbare Wirkung auf den Wert des Ausdrucks.

Natürlich habe ich es nie benutzt ..

Es soll möglich sein, einen Algorithmus Komplexität zu bewerten. Dies in Kombination mit der Kenntnis, wie viele Elemente es dauern wird Ihnen helfen kann, um zu bestimmen, ob es schlecht geeignet für seine Aufgabe ist.

Er sagt, wie viele Iterationen ein Algorithmus im schlimmsten Fall hat.

für ein Element in einer Liste zu suchen, können Sie die Liste durchlaufen, bis Sie das Einzelteil erhalten. Im schlimmsten Fall ist der Punkt auf dem letzten Platz.

Nehmen wir es n Elemente in der Liste. Im schlimmsten Fall nehmen Sie n Iterationen. Im Big O notiation ist es O (n).

Es sagt factualy, wie effizient ein Algorithmus ist.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top