Wie lautet eine einfache englische Erklärung der "Big O"-Notation?

Question

Ich bevorzuge so wenig formale Definitionen wie möglich und einfache Mathematik.

Answer 1

Die einfachste Art, dies zu betrachten (in einfachem Englisch)

Wir versuchen herauszufinden, wie sich die Anzahl der Eingabeparameter auf die Laufzeit eines Algorithmus auswirkt. Wenn die Laufzeit Ihrer Anwendung proportional zur Anzahl der Eingabeparameter ist, dann spricht man von Big O von n.

Die obige Aussage ist ein guter Anfang, aber nicht ganz richtig.

Eine genauere Erklärung (mathematisch)

Angenommen,

n=Anzahl der Eingabeparameter

T(n)= Die eigentliche Funktion, die die Laufzeit des Algorithmus als Funktion von n ausdrückt

c= eine Konstante

f(n)= Eine Näherungsfunktion, die die Laufzeit des Algorithmus als Funktion von n ausdrückt

Was Big O betrifft, so wird die Annäherung f(n) als gut genug angesehen, solange die folgende Bedingung erfüllt ist.

lim     T(n)  c×f(n)
n

Die Gleichung lautet wie folgt Wenn sich n der Unendlichkeit nähert, ist T von n kleiner als oder gleich c mal f von n.

In Big-O-Notation wird dies wie folgt geschrieben

T(n)O(n)

Dies wird gelesen als T von n ist in groß O von n.

Zurück zu Englisch

Ausgehend von der obigen mathematischen Definition bedeutet die Aussage, dass Ihr Algorithmus ein Big O von n ist, dass er eine Funktion von n (Anzahl der Eingabeparameter) ist oder schneller . Wenn Ihr Algorithmus Big O von n ist, dann ist er auch automatisch das Big O von n Quadrat.

Big O von n bedeutet, dass mein Algorithmus mindestens so schnell läuft wie dieser. Sie können nicht auf die Big O Notation Ihres Algorithmus schauen und sagen, dass er langsam ist. Sie können nur sagen, dass er schnell ist.

Vérifiez diese für ein Video-Tutorial über Big O von der UC Berkley aus. Es ist eigentlich ein einfaches Konzept. Wenn Sie Professor Shewchuck (auch bekannt als Lehrer auf Gottesebene) hören, wie er es erklärt, werden Sie sagen: "Oh, das ist alles!".

Answer 2

Ich habe eine wirklich großartige Erklärung der Big-O-Notation gefunden, besonders für jemanden, der sich nicht so sehr für Mathematik interessiert.

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Die Big-O-Notation wird in der Informatik verwendet, um die Leistung zu beschreiben oder Komplexität eines Algorithmus zu beschreiben. Big O beschreibt insbesondere die Worst-Case-Szenario und kann verwendet werden, um die Ausführungszeit zu beschreiben Ausführungszeit oder den von einem Algorithmus beanspruchten Platz (z. B. im Speicher oder auf der Festplatte) Algorithmus.

Jeder, der Programming Pearls oder ein anderes Informatikbuch gelesen hat Bücher gelesen hat und keine Grundkenntnisse in Mathematik hat, wird gegen eine Wand gestoßen sein wenn er auf Kapitel stößt, in denen O(N log N) oder andere scheinbar verrückte Syntax. Ich hoffe, dass dieser Artikel Ihnen hilft, ein Verständnis für die Grundlagen von Big O und Logarithmen.

Da ich in erster Linie Programmierer und in zweiter Linie Mathematiker bin (oder vielleicht in dritter oder vierter vierte) fand ich, dass der beste Weg, Big O gründlich zu verstehen, darin bestand einige Beispiele in Code zu erstellen. Im Folgenden finden Sie also einige gängige Wachstum zusammen mit Beschreibungen und Beispielen, wo möglich.

O(1)

O(1) beschreibt einen Algorithmus, der immer in der gleichen Zeit ausgeführt wird (oder Platz) benötigt, unabhängig von der Größe des Eingabedatensatzes.

bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null;
}

O(N)

O(N) beschreibt einen Algorithmus, dessen Leistung linear wächst und direkt proportional zur Größe des Eingabedatensatzes wächst. Das Beispiel unten zeigt auch, dass Big O das Worst-Case-Szenario begünstigt Szenario begünstigt; eine übereinstimmende Zeichenkette könnte während jeder Iteration der for-Schleife gefunden werden und die Funktion würde vorzeitig zurückkehren, aber die Big-O-Notation aber die Big-O-Notation geht immer von der Obergrenze aus, bei der der Algorithmus die maximale Anzahl von Iterationen durchführt.

bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 

O(N 2 )

O(N 2 ) stellt einen Algorithmus dar, dessen Leistung direkt proportional zum Quadrat der Größe des Eingabedatensatzes ist. Dies ist bei Algorithmen üblich, die verschachtelte Iterationen über den Datensatz Datensatz beinhalten. Tiefer geschachtelte Iterationen führen zu O(N 3 ), O(N 4 ) usw.

bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

O(2 N )

O(2 N ) bezeichnet einen Algorithmus, dessen Wachstum sich mit jeder Erweiterung des dem Eingabedatensatz verdoppelt. Die Wachstumskurve eines O(2 N ) Funktion ist exponentiell - sie beginnt sehr flach und steigt dann kometenhaft an. Ein Beispiel für eine O(2 N ) Funktion ist die rekursive Berechnung von Fibonacci Zahlen:

int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

Logarithmen

Logarithmen sind etwas schwieriger zu erklären, daher verwende ich eine allgemeine Beispiel:

Die binäre Suche ist eine Technik zum Durchsuchen sortierter Datensätze. Sie funktioniert durch Auswahl des mittleren Elements des Datensatzes, im Wesentlichen des Median, und vergleicht es mit einem Zielwert. Wenn die Werte übereinstimmen, wird Erfolg zurück. Wenn der Zielwert höher ist als der Wert des als der Wert des Probeelements, wird die obere Hälfte des Datensatzes genommen und und führt den gleichen Vorgang mit diesem durch. Wenn der Zielwert niedriger als der Wert des Probeelements ist, wird die Operation Operation mit der unteren Hälfte durch. Die Halbierung des Datensatzes wird mit jeder Iteration fortgesetzt Datenmenge so lange zu halbieren, bis der Wert gefunden wurde oder bis die den Datensatz nicht mehr aufteilen kann.

Diese Art von Algorithmus wird als O(log N) beschrieben. Die iterative Halbierung von Datensätzen, wie im Beispiel der binären Suche beschrieben, ergibt eine Wachstumskurve, die zu Beginn ihren Höhepunkt erreicht und mit zunehmender Größe der der Datensätze langsam abflacht, z. B. ein Eingabedatensatz mit 10 Elementen eine Sekunde, ein Datensatz mit 100 Einträgen benötigt zwei Sekunden, und ein Datensatz mit 1000 Einträgen benötigt drei Sekunden. Die Verdoppelung der Größe des Eingabedatensatzes hat nur geringe Auswirkungen auf Wachstum, da der Datensatz nach einer einzigen Iteration des Algorithmus des Algorithmus halbiert wird und somit einem halb so großen Eingabedatensatz gleichkommt. Größe. Dies macht Algorithmen wie die binäre Suche extrem effizient wenn sie mit großen Datensätzen arbeiten.

Answer 3

Vorwort

Algorithmus Verfahren/Formel zur Lösung eines Problems

---

Wie lassen sich Algorithmen analysieren und wie können wir Algorithmen miteinander vergleichen?

Beispiel: Sie und ein Freund sollen eine Funktion erstellen, um die Zahlen von 0 bis N zu summieren. Sie kommen auf f(x) und Ihr Freund auf g(x). Beide Funktionen haben das gleiche Ergebnis, aber einen unterschiedlichen Algorithmus. Um die Effizienz der Algorithmen objektiv zu vergleichen, verwenden wir Big-O-Notation .

Big-O-Notation: beschreibt wie schnell die Laufzeit im Verhältnis zur Eingabe ansteigt, wenn die Eingabe beliebig groß wird.

3 wichtige Erkenntnisse:

1. Vergleichen Sie wie schnell die Laufzeit wächst NICHT genaue Laufzeiten vergleichen (abhängig von der Hardware)
2. Es geht nur um die Laufzeit, die relativ zur Eingabe wächst. (n)
3. Als n beliebig groß wird, konzentrieren Sie sich auf die Terme, die am schnellsten wachsen, wenn n groß wird (denken Sie an unendlich) AKA asymptotische Analyse

Raumkomplexität: Neben der Zeitkomplexität interessiert uns auch die Raumkomplexität (wie viel Speicherplatz ein Algorithmus benötigt). Anstatt die Zeit der Operationen zu prüfen, prüfen wir die Größe der Speicherzuweisung.

Answer 4

Dies ist eine sehr vereinfachte Erklärung, aber ich hoffe, sie deckt die wichtigsten Details ab.

Nehmen wir an, Ihr Algorithmus zur Lösung des Problems hängt von einigen "Faktoren" ab, zum Beispiel von N und X.

Je nach N und X erfordert Ihr Algorithmus einige Operationen, zum Beispiel im WORST-Fall 3(N^2) + log(X) Operationen.

Da Big-O sich nicht allzu sehr um den konstanten Faktor (aka 3) kümmert, ist das Big-O Ihres Algorithmus O(N^2 + log(X)) . Im Grunde bedeutet dies: "Die Anzahl der Operationen, die Ihr Algorithmus im schlimmsten Fall benötigt, skaliert mit diesem Wert".

Answer 5

Das große O ist ein Mittel zur Darstellung der oberen Grenzen einer beliebigen Funktion. Wir verwenden es im Allgemeinen, um die oberen Schranken einer Funktion auszudrücken, die die Laufzeit eines Algorithmus angibt.

Beispiel: f(n) = 2(n^2) +3n ist eine Funktion, die die Laufzeit eines hypothetischen Algorithmus darstellt. Die Big-O-Notation gibt im Wesentlichen die Obergrenze für diese Funktion an, die O(n^2) ist.

Diese Notation besagt im Grunde, dass die Laufzeit für jede beliebige Eingabe 'n' nicht größer sein wird als der Wert, der durch die Big-O-Notation ausgedrückt wird.

Außerdem stimme ich mit allen oben genannten ausführlichen Antworten überein. Hoffentlich hilft das!