Big-O für Achtjährige?[Duplikat]

Question

Auf diese Frage gibt es hier bereits eine Antwort:

• Was ist eine einfache englische Erklärung der „Big O“-Notation? 39 Antworten

Ich frage mehr darüber, was das für meinen Code bedeutet.Ich verstehe die Konzepte mathematisch, es fällt mir nur schwer, mir klarzumachen, was sie konzeptionell bedeuten.Wenn man beispielsweise eine O(1)-Operation an einer Datenstruktur durchführen würde, verstehe ich, dass die Anzahl der auszuführenden Operationen nicht zunimmt, weil mehr Elemente vorhanden sind.Und eine O(n)-Operation würde bedeuten, dass Sie für jedes Element eine Reihe von Operationen ausführen würden.Könnte hier jemand die Lücken füllen?

• Was genau würde eine O(n^2)-Operation bewirken?
• Und was zum Teufel bedeutet es, wenn eine Operation O(n log(n)) ist?
• Und muss jemand Crack rauchen, um ein O(x!) zu schreiben?

Answer 1

Eine Möglichkeit, darüber nachzudenken, ist dies:

O (N ^ 2) bedeutet, für jedes Element, bist du etwas mit jedem anderen Elemente zu tun, wie sie zu vergleichen. Bubble-Sort ist ein Beispiel dafür.

O (N log N) bedeutet, für jedes Element, sind Sie etwas zu tun, die nur bei log N der Elemente zu suchen braucht. Dies ist in der Regel, weil Sie etwas über die Elemente kennen, können Sie eine effiziente Wahl treffen. Effizienteste Art ist ein Beispiel dafür, wie Mergesort.

O (N!) Bedeutet etwas für alle möglichen Permutationen der N Elemente zu tun. Verkäufer Reisen ist ein Beispiel dafür, wo es N ist! Möglichkeiten, um die Knoten zu besuchen, und die Brute-Force-Lösung ist bei den Gesamtkosten von jeder möglichen Permutation zu suchen, die optimalen zu finden.

Answer 2

Die große Sache, die Big-O-Notation, um Ihren Code bedeutet, ist, wie es skaliert, wenn man die Menge der „Dinge“ verdoppeln arbeitet auf. Hier ist ein konkretes Beispiel:

Big-O       |  computations for 10 things |  computations for 100 things
----------------------------------------------------------------------
O(1)        |   1                         |     1
O(log(n))   |   3                         |     7
O(n)        |  10                         |   100
O(n log(n)) |  30                         |   700
O(n^2)      | 100                         | 10000

So nehmen quicksort die O (n log (n)) vs Blasensortierung, die O (n ^ 2). Wenn 10 Dinge sortieren, quicksort ist 3-mal schneller als Bubble-Sort. Aber wenn 100 Dinge sortieren, ist es 14-mal schneller! Eindeutig den schnellsten Algorithmus Kommissionierung ist wichtig, dann. Wenn Sie zu Datenbanken mit Millionen Zeilen erhalten, können sie den Unterschied zwischen Ihrer Anfrage bedeuten in 0,2 Sekunden ausgeführt wird, im Vergleich zu Stunden.

Eine andere Sache zu prüfen ist, dass ein schlechter Algorithmus eine Sache, die Moores Gesetz kann nicht helfen, ist. Zum Beispiel haben, wenn Sie einige wissenschaftliche Berechnung bekommen, die O (n ^ 3), und es kann 100 Dinge, die einen Tag berechnen, eine Verdoppelung die Prozessorgeschwindigkeit bekommt man nur 125 Dinge an einem Tag. Allerdings stößt diese Berechnung auf O (n ^ 2) und du tust 1000 Dinge am Tag.

Klarstellung: Eigentlich Big-O sagt nichts über vergleichende Leistung verschiedener Algorithmen zum gleichen bestimmten Größe Punkt, sondern um vergleichende Leistung des gleichen Algorithmus bei unterschiedlicher Größe Punkten:

                 computations     computations       computations
Big-O       |   for 10 things |  for 100 things |  for 1000 things
----------------------------------------------------------------------
O(1)        |        1        |        1        |         1
O(log(n))   |        1        |        3        |         7
O(n)        |        1        |       10        |       100
O(n log(n)) |        1        |       33        |       664
O(n^2)      |        1        |      100        |     10000

Answer 3

Sie finden es möglicherweise nützlich es sichtbar zu machen:

Auch auf LogY / LogX skalieren die Funktionen n ^1/2 , n, n ² all aussehen wie gerade Linien , während auf LogY / X Skala 2 ⁿ , e ⁿ 10 ⁿ sind gerade Linien und n ist linearithmic (sieht aus wie n log n ).

Answer 4

Dies könnte zu mathematisch, aber hier ist mein Versuch. (I am ein Mathematiker.)

Wenn etwas O ( f ( n )), dann auf seine Laufzeit n werden Elemente gleich A f ( n ) + B (gemessen in, sagen wir, Taktzyklen oder CPU-Operationen). Es ist Schlüssel zum Verständnis, dass Sie auch diese Konstanten A und B , die sich aus der konkreten Umsetzung entstehen. B stellt im Wesentlichen die „konstante Overhead“ Ihres Betriebs, zum Beispiel einige Vorverarbeitung, dass Sie das tun, nicht auf die Größe der Sammlung abhängt. A steht für die Geschwindigkeit Ihres aktuellen Artikel-Verarbeitungsalgorithmus.

Der Schlüssel ist jedoch, dass Sie O-Notation verwenden, um herauszufinden, , wie gut etwas skalieren . Das heißt, diese Konstanten werden nicht wirklich wichtig: wenn Sie versuchen, herauszufinden, wie 10-10000 Artikel zu skalieren, wer kümmert sich um die konstante Overhead B ? Auch andere Bedenken (siehe unten) werden überwiegen sicherlich das Gewicht der multiplikative Konstante A .

So ist der real deal f ( n ). Wenn f wächst nicht mit n , z.B. f ( n ) = 1, dann werden Sie fantastisch --- Ihre Laufzeit immer nur skaliert A + B . Wenn f wächst linear mit n , dh f ( n ) = n , Ihre Laufzeit wird so ziemlich so gut skalieren, wie erwartet werden kann, --- wenn die Benutzer 10 10 ns für Elemente darauf warten, sie 10000 ns für 10000 Elemente (ohne Berücksichtigung der additiven konstante) warten werde. Aber wenn es schneller wächst, wie n ² , dann bist du in Schwierigkeiten; Dinge beginnen zu viel langsamer, wenn Sie größere Sammlungen erhalten. f ( n ) = n log ( n ) ist ein guter Kompromiss, in der Regel: Ihr Betrieb kann nicht werden so einfach wie lineare Skalierung zu geben, aber Sie haben es geschafft, die Dinge zu reduzieren, so dass es wird skaliert viel besser als f ( n ) = n ² .

Praktisch sind hier einige gute Beispiele:

• O (1): ein Element aus einem Array abruft. Wir wissen genau, wo sie in Erinnerung ist, so dass wir es einfach gehen zu bekommen. Dabei spielt es keine Rolle, ob die Sammlung 10 Stück oder 10000 hat; es ist immer noch am Index (sagen wir) 3, so dass wir nur an Position 3 im Speicher springen.
• O ( n ): ein Element aus einer verketteten Liste abruft. Hier A = 0,5, da im Durchschnitt you''ll durch 1/2 der Liste gehen, bevor Sie das Element Sie suchen finden.
• O ( n ² ): divers "dumm" Sortieralgorithmen. Da im Allgemeinen ihre Strategie beinhaltet, für jedes Element ( n ), Sie sehen alle anderen Elemente (so mal eine andere n , so dass n < sup> 2 ), dann sich an der richtigen Stelle positionieren.
• O ( n log ( n )): verschiedene "intelligente" Sortieralgorithmen. Es stellt sich heraus, dass man nur schauen müssen, sagen wir, 10 Elemente in 10 ¹⁰ -Element Sammlung intelligent zu sortieren, sich in Bezug auf alle sonst in der Sammlung. Weil jeder andere ist auch geht auf 10 Elemente zu sehen, und das austretende Verhalten ist genau richtig orchestriert so, dass dies genug, um eine sortierte Liste zu erzeugen.
• O ( n !): Ein Algorithmus, der "alles versucht", da es (proportional) n ! mögliche Kombinationen von n -Elemente, die ein bestimmtes Problem lösen könnte. So ist es Schleifen nur durch alle solche Kombinationen, versucht sie, stoppt dann, wenn es gelingt.

Answer 5

don.neufeld Antwort ist sehr gut, aber ich würde es wahrscheinlich in zwei Teilen erklären: Erstens, es gibt eine grobe Hierarchie von O () 's, dass die meisten Algorithmen fallen in. Dann können Sie an jeden von denen schauen, um mit Skizzen von dem, was typische Algorithmen dieser Zeit Komplexität zu tun.

Für praktische Zwecke der einzige O () 's, dass je Rolle zu spielen sind:

• O (1) „konstante Zeit“ - die erforderliche Zeit ist unabhängig von der Größe des Eingangs. Als grobe Kategorie, würde ich Algorithmen wie Hash-Lookups und umfasst Union-Find hier, auch wenn keiner von denen ist wirklich O (1).
• O (log (n)) „logarithmische“ - es wird langsamer, wie Sie größere Eingänge erhalten, aber sobald Sie Ihre Eingabe ziemlich groß wird, wird es nicht genug Sorgen ändern. Wenn Ihre Laufzeit mit üblichen Größe Daten in Ordnung ist, können Sie es mit so vielen zusätzlichen Daten überschwemmen, wie Sie wollen, und es wird immer noch in Ordnung sein.
• O (n) "linear" - je mehr Input, desto länger dauert es, in einem noch Kompromiss. Dreimal die Eingangsgröße so lange etwa dreimal dauern.
• O (n log (n)) "besser als quadratische" - Erhöhung der Eingangsgröße tut weh, aber es ist immer noch überschaubar. Der Algorithmus ist wahrscheinlich in Ordnung, es ist nur, dass das zugrunde liegende Problem ist schwieriger (Entscheidungen weniger sind in Bezug auf die Eingangsdaten lokalisiert) als jene Probleme, die in linearer Zeit gelöst werden können. Wenn Sie Ihre Eingabe Größen dort Aufstehen sind, nicht davon ausgehen, dass Sie unbedingt doppelt so groß wie handhaben könnte Ihre Architektur um ohne Veränderung (zB durch Dinge über Nacht Batch-Berechnungen bewegen, oder die Dinge nicht pro-Rahmen zu tun). Es ist in Ordnung, wenn die Eingangsgröße ein wenig erhöht, obwohl; achten Sie nur für ein Vielfaches.
• O (n ^ 2) „quadratische“ - es ist wirklich nur auf eine bestimmte Größe Ihrer Eingabe aufzuarbeiten gehen, so achten Sie auf, wie groß es bekommen konnte. Auch Ihr Algorithmus saugen kann - man denke schwer zu sehen, ob es ein O (n log (n)) Algorithmus, Sie würden, was Sie brauchen. Sobald Sie hier sind, fühlen sich sehr dankbar für die erstaunliche Hardware haben wir mit begabt. Vor nicht langer Zeit, was Sie versuchen, unmöglich wäre zu tun gewesen für alle praktischen Zwecke.
• O (n ^ 3) "cubic" - qualitativ nicht so verschieden von O (n ^ 2). Die gleichen Bemerkungen gelten, nur um so mehr. Es gibt eine gute Chance, dass ein cleverer Algorithmus diesmal nach unten kleiner etwas rasieren könnte, zB O (n ^ 2 log (n)) oder O (n ^ 2,8 ...), aber dann wieder, es gibt eine gute Chance, dass es wird nicht die Mühe wert sein. (Sie sind bereits in Ihrer praktischen Eingangsgröße begrenzt, so dass die konstanten Faktoren, die für die cleveren Algorithmen erforderlich sein können, werden wahrscheinlich überschwemmen ihre Vorteile für die praktischen Fälle auch Denken langsam;. Die Computer kauen lassen darauf Ihnen Zeit sparen kann Gesamt.)
• O (2 ^ n) "exponential" - das Problem ist entweder grundsätzlich rechnerisch schwer oder du ein Idiot bist zu sein. Diese Probleme haben einen erkennbaren Geschmack zu ihnen. Ihre Eingangsgrößen werden mit einer ziemlich spezifischen harten Grenze begrenzt. Sie werden schnell wissen, ob Sie in dieser Grenze passen.

Und das ist es. Es gibt viele andere Möglichkeiten, die zwischen diesem (oder größer sind als O (2 ^ n)) passen, aber sie oft in der Praxis nicht passieren, und sie sind qualitativ nicht sehr verschieden von einem von ihnen. Cubic Algorithmen sind bereits bisschen weit hergeholt; Ich enthalten sie nur, weil ich in ihnen oft genug gelaufen sind erwähnenswert (zB Matrix-Multiplikation) zu sein.

Was passiert eigentlich für diese Klassen von Algorithmen? Nun, ich glaube, Sie hatte einen guten Start, aber es gibt viele Beispiele, die diese Charakterisierungen nicht passen würde. Aber für die oben, würde ich sagen, es geht in der Regel so etwas wie:

• O (1) - Sie sind nur höchstens an einer festen Größe Teil Ihrer Eingangsdaten suchen und möglicherweise nichts davon. Beispiel: das Maximum einer sortierten Liste.
  • Oder Ihre Eingabegröße ist begrenzt. Beispiel: Addition zweier Zahlen. (Beachten Sie, dass die Zugabe von N Zahlen ist die lineare Zeit).
• O (log n) - jedes Element Ihrer Eingabe sagt Ihnen, genug, um einen großen Anteil an den Rest des Eingangs zu ignorieren. Beispiel: Wenn Sie bei einem Array-Elemente in binärer Suche suchen, ihr Wert sagt Ihnen, dass Sie „Hälfte“ des Array, ohne auf irgendetwas davon ignorieren können. Oder ähnlich, das Element, das Sie schauen, haben Sie genug von einer Zusammenfassung von einem Bruchteil der verbleibenden Eingang, dass Sie nicht um es betrachten müssen.
  • Es gibt nichts Besonderes Hälften, obwohl - wenn Sie nur 10% Ihrer Eingabe bei jedem Schritt ignorieren können, ist es noch logarithmisch
  .
• O (n) - Sie haben einige festgelegte Menge an Arbeit pro Eingabeelement. (Aber siehe unten).
• O (n log (n)) - es gibt ein paar Varianten.
  • Sie kann die Eingabe in zwei Stapel aufzuteilen (in nicht mehr als linearer Zeit), das Problem lösen und unabhängig an jedem Stapel, und dann verbindet die zwei Stapel die endgültige Lösung zu bilden. Die Unabhängigkeit der beiden Pfähle ist der Schlüssel. Beispiel:. Klassische rekursive mergesort
  • Jeder linearen Zeitdurchlauf über die Daten bekommt man auf halben Weg zu Ihrer Lösung. Beispiel:. Quicksort wenn Sie in Bezug auf den maximalen Abstand von jedem Element in seine endgültige sortiert Position bei jedem Teilungsschritt denken (und ja, ich weiß, dass es tatsächlich O (n ^ 2) wegen degenerierten Gelenk Entscheidungen Aber praktisch gesehen, es fällt in meine O (n log (n)) Kategorie).
• O (n ^ 2) - Sie haben bei jedem Paar von Eingabeelementen zu suchen.
  • Oder Sie dies nicht tun, aber Sie denken, Sie tun, und Sie verwenden den falschen Algorithmus.
• O (n ^ 3) - äh ... Ich habe keine flotte Charakterisierung von dieser habe. Es ist wahrscheinlich eines der folgenden:
  • Sie multiplizieren Matrizen
  • Sie befinden sich in jedem Paar Eingänge aber die Operation erfordert, dass Sie wieder an allen Eingängen der Suche zu tun
  • die gesamte Grafik Struktur Ihrer Eingabe ist relevant
• O (2 ^ n) - Sie müssen jede mögliche Teilmenge der Eingaben prüfen
.

Keiner von ihnen sind streng. Schon gar nicht linearen Zeitalgorithmen (O (n)): I mit einer Reihe von Beispielen kommen konnte, wo man an allen Eingängen schauen müssen, dann die Hälfte von ihnen, dann die Hälfte derer, etc. Oder umgekehrt - - Sie falten zusammen Paare von Eingängen, dann auf den Ausgang Rekursion. Diese passen nicht die Beschreibung oben, da Sie nicht einmal an jedem Eingang suchen, aber es kommt immer noch in linearer Zeit aus. Dennoch bedeutet 99,2% der Zeit, die lineare Zeit einmal an jedem Eingang suchen.

Answer 6

Viele von ihnen sind leicht mit etwas Nicht-Programmierung, wie Mischen der Karten zeigen.

Sortieranlagen ein Deck von Karten, indem sie durch das ganze Deck gehe die Pik-As zu finden, die dann durch das ganze Deck geht die 2 Pik zu finden, und so wäre schlimmster Fall sein n ^ 2, wenn das Deck schon ist nach hinten sortiert. Sie sah alle 52 Karten 52 mal.

Im Allgemeinen sind die wirklich schlechten Algorithmen sind nicht unbedingt gewollt, sie sind häufig ein Missbrauch von etwas anderes, wie eine Methode aufrufen, die linear innerhalb einer anderen Methode, die linear über den gleichen Satz wiederholt.

Answer 7

Okay, es gibt hier einige sehr gute Antworten, aber fast alle scheinen den gleichen Fehler zu machen, und dieser Fehler ist weit verbreitet.

Informell schreiben wir, dass f(n) = O( g(n) ), wenn g(n) bis zu einem Skalierungsfaktor und für alle n größer als ein n0 ist größer als f(n).Das heißt, f(n) wächst nicht schneller als, oder ist von oben begrenzt von, g(n).Dies sagt uns nichts darüber, wie schnell f(n) wächst, außer der Tatsache, dass es garantiert nicht schlechter als g(n) ist.

Ein konkretes Beispiel:n = O( 2^n ).Wir alle wissen, dass n viel weniger schnell wächst als 2^n, daher können wir sagen, dass es durch die oben angegebene Exponentialfunktion begrenzt ist.Zwischen n und 2^n ist viel Platz, daher ist es nicht sehr eng gebunden, aber es ist immer noch eine legitime Grenze.

Warum verwenden wir (Informatiker) Grenzen, anstatt genau zu sein?Denn a) Grenzen sind oft einfacher zu beweisen und b) es gibt uns eine Abkürzung, um Eigenschaften von Algorithmen auszudrücken.Wenn ich sage, dass mein neuer Algorithmus O(n.log n) ist, bedeutet das, dass seine Laufzeit im schlimmsten Fall von oben durch n.log n auf n Eingaben begrenzt wird, wenn n groß genug ist (siehe jedoch meine Kommentare unten). wenn ich vielleicht nicht den schlimmsten Fall meine).

Wenn wir stattdessen sagen wollen, dass eine Funktion genauso schnell wächst wie eine andere Funktion, verwenden wir Theta um diesen Punkt zu verdeutlichen (ich schreibe T( f(n) ), um heta von f(n) im Markdown zu bedeuten).T( g(n) ) ist die Abkürzung für „begrenzt von“. oberhalb und unterhalb durch g(n), wiederum bis auf einen Skalierungsfaktor und asymptotisch.

Das heißt f(n) = T( g(n) ) <=> f(n) = O(g(n)) und g(n) = O(f(n)).In unserem Beispiel können wir sehen, dass n != T( 2^n ), weil 2^n != O(n).

Warum sollte man sich darüber Sorgen machen?Denn in Ihrer Frage schreiben Sie: "Würde jemand rauchen, um ein o (x!) Zu schreiben?" Die Antwort lautet Nein - denn im Grunde genommen wird alles, was Sie schreiben, von der faktoriellen Funktion begrenzt.Die Laufzeit von Quicksort beträgt O(n!) – es ist einfach keine feste Grenze.

Es gibt hier auch eine andere Dimension der Subtilität.Normalerweise sprechen wir über die Worst-Case-Eingabe wenn wir die O(g(n))-Notation verwenden, sodass wir eine zusammengesetzte Aussage machen:Im schlimmsten Fall der Laufzeit wird es nicht schlechter sein als ein Algorithmus, der g(n) Schritte benötigt, wiederum Modulo-Skalierung und für ausreichend große n.Aber manchmal möchten wir über die Laufzeit des sprechen Durchschnitt und selbst am besten Fälle.

Vanilla Quicksort ist wie immer ein gutes Beispiel.Im schlimmsten Fall ist es T( n^2 ) (es werden tatsächlich mindestens n^2 Schritte benötigt, aber nicht wesentlich mehr), aber im Durchschnittsfall ist es T(n.log n), also die erwartete Anzahl von Schritte ist proportional zu n.log n.Im besten Fall ist es auch T(n.log n) – aber Sie könnten das verbessern, indem Sie beispielsweise überprüfen, ob das Array bereits sortiert wurde. In diesem Fall wäre die Laufzeit im besten Fall T( n ).

Wie hängt das mit Ihrer Frage nach der praktischen Umsetzung dieser Grenzen zusammen?Nun, leider verbirgt die O( )-Notation Konstanten, mit denen sich reale Implementierungen befassen müssen.Obwohl wir beispielsweise sagen können, dass wir für eine T(n^2)-Operation jedes mögliche Paar von Elementen besuchen müssen, wissen wir nicht, wie oft wir sie besuchen müssen (außer dass es keine Funktion von ist). N).Wir müssten also möglicherweise jedes Paar 10 Mal oder 10^10 Mal besuchen, und die T(n^2)-Anweisung macht keinen Unterschied.Auch Funktionen niedrigerer Ordnung sind ausgeblendet – wir müssten möglicherweise jedes Elementpaar einmal und jedes einzelne Element 100 Mal besuchen, weil n^2 + 100n = T(n^2).Die Idee hinter der O( )-Notation ist, dass dies für ein ausreichend großes n überhaupt keine Rolle spielt, da n^2 so viel größer als 100n wird, dass wir den Einfluss von 100n auf die Laufzeit nicht einmal bemerken.Allerdings haben wir es oft mit „ausreichend kleinen“ n zu tun, so dass konstante Faktoren usw. einen echten, signifikanten Unterschied machen.

Beispielsweise sind Quicksort (durchschnittliche Kosten T(n.log n)) und Heapsort (durchschnittliche Kosten T(n.log n)) beide Sortieralgorithmen mit den gleichen durchschnittlichen Kosten – dennoch ist Quicksort normalerweise viel schneller als Heapsort.Dies liegt daran, dass Heapsort ein paar mehr Vergleiche pro Element durchführt als Quicksort.

Das soll nicht heißen, dass die O( )-Notation nutzlos, sondern nur ungenau ist.Es ist ein ziemlich stumpfes Werkzeug für kleine N.

(Als letzte Anmerkung zu dieser Abhandlung sei daran erinnert, dass die O( )-Notation nur das Wachstum einer Funktion beschreibt – es muss nicht unbedingt die Zeit sein, es könnte sich um Speicher, in einem verteilten System ausgetauschte Nachrichten oder die Anzahl der erforderlichen CPUs handeln ein paralleler Algorithmus.)

Answer 8

Ich versuche, indem sie einfache Codebeispiele in C # zu erklären.

Für List<int> numbers = new List<int> {1,2,3,4,5,6,7,12,543,7};

O (1) sieht aus wie

return numbers.First();

O (n) sieht aus wie

int result = 0;
foreach (int num in numbers)
{
    result += num;
}
return result;

O (n log (n)) sieht aus wie

int result = 0;
foreach (int num in numbers)
{
    int index = numbers.length - 1;
    while (index > 1)
    {
        // yeah, stupid, but couldn't come up with something more useful :-(
        result += numbers[index];
        index /= 2;
    }
}
return result;

O (n ^ 2) sieht aus wie

int result = 0;
foreach (int outerNum in numbers)
{
    foreach (int innerNum in numbers)
    {
        result += outerNum * innerNum;
    }
}
return result;

O (n!) Sieht aus wie, ähm, zu müde, um mit irgendetwas zu kommen einfach.
Aber ich hoffe, dass Sie den allgemeinen Punkt?

Answer 9

So wie ich es meine nontechnical Freunde beschreiben, ist wie folgt:

Betrachten mehrstellige zusätzlich. Good old-fashioned, Bleistift und Papier hinaus. Die Art haben Sie erfahren, wenn Sie 7-8 Jahre alt waren. Gegeben seien zwei drei- oder vierstellige Zahlen, können Sie herausfinden, was sie summieren sich zu ziemlich leicht.

Wenn ich Ihnen zwei 100-stelligen Zahlen, und fragte sie, was sie addieren sich zu, es herauszufinden, wäre ziemlich einfach sein, auch wenn Sie Bleistift und Papier zu verwenden hatte. Ein helles Kind tun könnte ein solcher Zusatz in nur wenigen Minuten. Dies würde nur etwa 100 Operationen erfordern.

Betrachten Sie nun mehrstelligen Multiplikation. Sie haben gelernt, wahrscheinlich, dass bei etwa 8 oder 9 Jahre alt. Sie (hoffentlich) haben viele sich wiederholende Bohrer die Mechanik dahinter zu lernen.

Nun stelle ich dir gegeben habe, die gleichen zwei 100-stelligen Zahlen und sagte Ihnen, um sie miteinander zu multiplizieren. Dies wäre ein viel, viel sein schwierigere Aufgabe, etwas, dass Sie Stunden zu tun, nehmen würde - und dass Sie sei unwahrscheinlich, ohne Fehler zu machen. Der Grund dafür ist, dass (diese Version von) Multiplikation ist O (n ^ 2); jede Ziffer in der unteren Reihe aufweist, indem jede Ziffer in der oberen Zahl multipliziert werden, so dass insgesamt etwa n ^ 2 Operationen zu verlassen. Im Fall der 100-stelligen Zahlen, das ist 10.000 Multiplikationen.

Answer 10

Nein, ein O (n) Algorithmus bedeutet nicht, es auf jedem Element eine Operation durchführen wird. Big-O-Notation gibt Ihnen einen Weg, um über die „Geschwindigkeit“ zu sprechen, von Ihnen von Ihrer tatsächlichen maschinenunabhängigen Algorithmus.

O (n) bedeutet, dass die Zeit, Ihr Algorithmus nehmen linear als Eingabe Erhöhung wächst. O (n ^ 2) bedeutet, dass die Zeit, Ihr Algorithmus wächst als das Quadrat der Eingabe nimmt. Und so weiter.

Answer 11

So wie ich darüber nachdenke, ist, haben Sie die Aufgabe, die Reinigung von einer bösen Bösewicht V ein Problem verursacht auf die N nimmt, und Sie müssen abschätzen, wie viel länger es Ihr Problem dauern wird, zu beenden, wenn er erhöht N.

O (1) -> steigender N wirklich macht keinen Unterschied überhaupt

O (log (N)) -> jedes Mal, V N verdoppelt, Sie haben eine zusätzliche Menge an Zeit T ausgeben, um die Aufgabe abzuschließen. V verdoppelt N wieder, und Sie verbringen die gleiche Menge.

O (N) -> jedes Mal, V N verdoppelt, verbringen Sie doppelt so viel Zeit

.

O (N ^ 2) -> jedes Mal, V N verdoppelt, Sie verbringen 4x so viel Zeit. (Es ist nicht fair !!!)

O (N log (N)). -> jedes Mal, V N verdoppelt, Sie verbringen doppelt so viel Zeit plus ein wenig mehr

Dies sind Grenzen eines Algorithmus; Informatiker beschreiben wollen, wie lange es für große Werte von N. nehmen wird (was wichtig wird, wenn Sie Zahlen Factoring, die in der Kryptographie verwendet werden - wenn die Computer um einen Faktor 10 beschleunigen, wie viele Bits tun Sie haben es zu benutzen sie noch 100 Jahre dauern, um sicherzustellen, wird Ihre Verschlüsselung und nicht nur 1 Jahr?)

brechen

Einige der Grenzen können seltsame Ausdrücke haben, wenn es einen Unterschied zu den beteiligten Personen macht. Ich habe Sachen wie O gesehen (N log (N) log (log (N))) irgendwo in Knuths Art of Computer Programming für einige Algorithmen. (Kann mich nicht erinnern, die man aus der Spitze von meinem Kopf)

Answer 12

Eine Sache, die nicht aus irgendeinem Grund berührt noch:

Wenn Sie Algorithmen mit Dingen wie O sehen (2 ^ n) oder O (n ^ 3) oder andere unangenehme Werte es bedeutet oft Sie gehen eine unvollkommene Antwort auf Ihr Problem zu haben, um zu akzeptieren, eine akzeptable Leistung zu erhalten .

Die richtige Lösungen, die wie folgt sprengen sind üblich, wenn mit Optimierungsproblemen beschäftigen. Eine nahezu richtige Antwort in einem vernünftigen Zeitrahmen geliefert wird, ist besser als eine richtige Antwort geliefert, lange nachdem die Maschine zu Staub zerfallen ist.

Betrachten Schach: Ich weiß es nicht genau das, was die richtige Lösung angesehen wird, aber es ist wahrscheinlich so etwas wie O (n ^ 50) oder noch schlimmer. Theoretisch ist es unmöglich für jeden Computer, um tatsächlich die richtige Antwort zu berechnen - auch wenn man jedes Teilchen im Universum als Rechenelement verwenden, um einen Betrieb in der minimal möglichen Zeit für das Leben des Universums durchführen Sie noch eine Menge Nullen übrig haben . (Ob ein Quantencomputer lösen kann, ist es eine andere Sache.)

Answer 13

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.

Answer 14

• Und hat jemand Riss rauchen ein O schreiben (x!)?

Nein, nur Prolog verwenden. Wenn Sie einen Sortieralgorithmus in Prolog zu schreiben, indem Sie gerade beschreiben, dass jedes Element größer sein sollte als die vorherigen, und lassen Sie die Sortierung Rückzieher machen, die O sein (x!). Auch bekannt als "Permutation sortieren".

Answer 15

Ich mag don neufeld Antwort, aber ich glaube ich etwas über O (n log n) hinzufügen kann.

Ein Algorithmus, der eine einfache divide verwendet und Strategie erobern wird wahrscheinlich O (log n) sein. Das einfachste Beispiel dafür ist ein etwas in einer sortierten Liste zu finden. Sie beginnen nicht am Anfang und scannen für sie. Sie gehen in der Mitte, entscheiden Sie, wenn Sie dann rückwärts oder vorwärts gehen sollte, springen auf halber Strecke auf den letzten Platz man sah, und wiederholen Sie dies, bis Sie den Artikel finden, die Sie suchen.

Wenn Sie den quicksort oder mergesort Algorithmen betrachten, werden Sie sehen, dass sie sowohl den Ansatz, die Liste der Teilung in zwei Hälften zu sortier, jede Hälfte Sortierung (mit dem gleichen Algorithmus rekursiv) und rekombiniert dann die beiden Hälften . Diese Art von rekursive divide und Strategie erobern wird O (n log n).

Wenn man darüber nachdenkt sorgfältig, werden Sie, dass quicksort sehen tut ein O (n) Partitionierungsalgorithmus auf die gesamten n Elemente, dann ist ein O (n) Partitionierungs zweimal auf n / 2 Elemente, dann 4-mal auf n / 4 Artikel, etc ..., bis Sie zu einer n-Partitionen auf 1 Stück (das ist entartet). Die Anzahl, wie oft man n in der Hälfte teilen, um 1 zu erhalten etwa n einzuloggen, und jeder Schritt ist O (n), so rekursiven Teile und Herrsche ist O (n log n). Mergesort baut die andere Art und Weise, beginnend mit n Rekombinationen von 1 Punkt und mit 1 Rekombination von n Elementen Finishing, wo die Rekombination von zwei sortierten Listen ist O (n).

Wie bei Risse Rauchen ein O zu schreiben (n!) Algorithmus, sind Sie, wenn Sie keine andere Wahl haben. Der Reiseproblem oben gegeben wird angenommen, dass ein solches Problem sein.

Answer 16

Die meisten Jon Bentley Bücher (z Programmierung Pearls ) decken solche Sachen in einer wirklich pragmatische Art und Weise. dieses Gespräch von ihm gegeben umfasst eine solche Analyse eines quicksort.

Während nicht ganz relevant für die Frage, Knuth kam mit einem interessante Idee : Unterricht Big-O-Notation in der High School Kalkül Klassen, obwohl ich diese Idee ziemlich exzentrisch finden.

Answer 17

Betrachten Sie es als lego Blöcke Stapel (n) vertikal und über sie zu springen.

O (1) bedeutet, bei jedem Schritt, was Sie tun nichts. Die Höhe bleibt gleich.

O (n) bedeutet, in jedem Schritt, stapeln Sie C-Blöcke, wobei C1 eine Konstante ist.

O (n ^ 2) bedeutet, bei jedem Schritt, man c2 x n Blöcke stapeln, wobei C2 eine Konstante ist, und n ist die Anzahl der gestapelten Blöcke.

O (n log n) bedeutet, in jedem Schritt, man c3 x n x log n Blöcke stapeln, wobei C3 eine Konstante ist, und n ist die Anzahl der gestapelten Blöcke.

Answer 18

Um zu verstehen, O (n log n), denken Sie daran, dass log n bedeutet log-base-2 von n. Dann ist an jedem Teil:

O (n) ist, mehr oder weniger, wenn Sie auf jedes Element in der Reihe arbeiten.

O (n log) ist, wenn die Anzahl der Operationen der gleiche wie der Exponent ist, zu dem Sie 2, erhöhen die Anzahl der Elemente zu erhalten. Eine binäre Suche, zum Beispiel, hat die Gruppe in halblogarithmischen n-mal schneiden.

O (n log n) ist eine Kombination - du bist in dem Satz für jedes Element etwas entlang der Linien von einer binären Suche zu tun. Effiziente Art arbeitet oft, indem Sie eine Schleife pro Stück, und in jeder Schleife eine gute Suche macht den richtigen Ort zu finden, das Element oder die Gruppe in Frage zu stellen. Daher n * log n.

Answer 19

Nur um das paar Kommentare zu meinem obigen Beitrag zu antworten:

Domenic - ich auf dieser Seite bin, und ich kümmere. Nicht für Pedanterie willen, sondern weil wir - als Programmierer - Pflege der Regel um Präzision. Mit O () Schreibweise falsch in dem Stil, der einige hier getan haben, macht es irgendwie sinnlos; wir können auch nur etwas sagen, n ^ 2 Zeiteinheiten als O nimmt (n ^ 2) unter den hier verwendeten Konventionen. Verwendung des O () fügt nichts. Es ist nicht nur eine kleine Diskrepanz zwischen dem gemeinsamen Nutzung und mathematischer Präzision, die ich spreche, es ist der Unterschied zwischen es sinnvoll zu sein und es nicht.

Ich kenne viele, viele hervorragende Programmierer, die diese Begriffe genau verwenden. Zu sagen, ‚oh, wir sind Programmierer deshalb nicht kümmern uns‘ verbilligt das ganze Unternehmen.

OneByOne - Nun, nicht wirklich, obwohl ich Ihren Punkt nehmen. Es ist nicht O (1) für beliebig große n, die Art der Definition von O ist (). Es geht nur, dass die O zu zeigen, () hat Anwendbarkeit für beschränkte n beschränkt, wo wir lieber tatsächlich über die Anzahl der zurückgelegten Schritte statt einem gebundenen auf diese Zahl sprechen.

Answer 20

Lassen Sie Ihre acht Jahre alten log (n) bedeutet, dass die Anzahl der Sie haben eine Länge n log in zwei hacken für sie Größe runter n = 1: p

O (n log n) ist in der Regel das Sortieren O (n ^ 2) ist in der Regel alle Paare von Elementen zu vergleichen

Answer 21

Angenommen, Sie einen Computer hatten, die ein Problem mit einer bestimmten Größe lösen könnte. Nun stell dir vor, dass wir die Leistung ein paar Mal verdoppeln können. Wie viel größer ein Problem können wir mit jeder Verdoppelung lösen?

Wenn wir ein Problem mit der doppelten Größe lösen können, das ist O (n).

Wenn wir einen Multiplikator haben, die keine ist, das ist eine Art von Polynom Komplexität. Zum Beispiel, wenn jede Verdoppelung uns erlaubt, um etwa 40% des Problems Größe zu erhöhen, ist es O (n ^ 2), und etwa 30% wäre O (n ^ 3).

Wenn wir nur auf die Problemgröße hinzufügen, es ist exponentiell oder schlechter. Wenn zum Beispiel jede Verdoppelung bedeutet, dass wir ein Problem 1 größer lösen können, ist es O (2 ^ n). (Aus diesem Grund-Brute zwingen einen Chiffrierschlüssel mit recht großen Tasten effektiv unmöglich wird: a. 128-Bit-Schlüssel benötigt etwa 16 Trillionen mal so viel Verarbeitung als 64-Bit)

Answer 22

Denken Sie an die Fabel von der Schildkröte und der Hase (Schildkröte und Kaninchen)?

Auf lange Sicht, die Schildkröte gewinnt, aber auf kurze Sicht die Hasen gewinnt.

Das ist wie O (log N) (Schildkröte) vs. O (N) (Hase).

Wenn zwei Methoden in ihre Big-O unterscheiden, dann gibt es eine Ebene von N, an dem einer von ihnen wird gewinnen, aber Big-O sagt nichts darüber, wie groß, dass N ist.

Answer 23

aufrichtig bleiben auf die Frage stellte ich die Frage in der Art und Weise beantworten würde ich ein 8 Jahre altes Kind antworten würde

Angenommen, ein Eisverkäufer eine Reihe von Eis bereitet (sagen N) in verschiedenen Formen in einer geordneten Art und Weise angeordnet ist. Sie wollen das Eis in der Mitte liegend essen

Fall 1: - Sie können nur ein Eis essen, wenn Sie alle Eis gegessen haben kleiner, als es Sie werden die Hälfte aller Eis essen vorbereitet (Eingang) .Answer hängt direkt von der Größe des Eingangs Lösung der Ordnung o sein (N)

Fall 2: - Sie können das Eis in der Mitte direkt essen

Solution O (1)

sein

Fall 3: Sie können ein Eis essen nur, wenn Sie alle Eissorten kleiner, als es gegessen haben und jedes Mal, wenn Sie ein Eis essen können Sie ein anderes Kind (neues Kind jedes Mal) alle Cremes sein Eis essen Insgesamt benötigte Zeit wäre N + N + N genommen ....... (N / 2) mal Lösung wird O (N2)

Answer 24

log (n) bedeutet logarithmische Wachstum. Ein Beispiel wäre Algorithmen teile und herrsche. Wenn Sie 1000 sortierten Zahlen in einem Array (ex. 3, 10, 34, 244, 1203 ...) und will für eine Nummer in der Liste suchen (seine Position finden), können Sie mit der Überprüfung des Wertes des Start Anzahl an Index 500. Wenn sie niedriger als das, was Sie suchen, zu 750. springen Wenn sie höher als das, was Sie suchen, springen bis 250. Dann Sie den Vorgang wiederholen, bis Sie Ihren Wert (und Schlüssel) finden. Jedes Mal, wenn wir die Hälfte der Suchraum springen, können wir keulen weg viele andere Werte zu testen, da wir die Zahl 3004 kann nicht über Nummer 5000 weiß (denken Sie daran, es ist eine sortierte Liste).

n log (n) dann bedeutet n * log (n).

Answer 25

Ich werde versuchen, um tatsächlich eine Erklärung für einen echten 8 Jahre alten Jungen zu schreiben, abgesehen von technischen Begriffe und mathematische Begriffe.

  

Wie, was genau würde ein O(n^2) Betrieb tun?

Wenn Sie in einer Gruppe sind, und es gibt n Leute in der Partei auch Sie. Wie viele Handschläge es so nehmen, dass jeder mit Handshake hat alle anderen gegeben, dass die Leute würden wahrscheinlich vergessen, die sie irgendwann mit Handshake.

. Hinweis: diese annähernd ein simplex Nachgeben n(n-1), die nahe genug ist, um n^2

  

Und was zum Teufel bedeutet es, wenn eine Operation O(n log(n)) ist?

Ihre Lieblingsmannschaft gewonnen hat, sie im Einklang steht, und es gibt n Spieler im Team. Wie viele hanshakes es würden Sie nehmen jeden Spieler zum Händedruck, da Sie jeweils ein mehrfach Hanshake wird, wie oft, wie viele Stellen in der Anzahl der Spieler n sind.

. Hinweis: dies ergibt n * log n to the base 10

  

Und hat jemand hat Crack rauchen eine O(x!) zu schreiben?

Sie sind ein reiches Kind und in Ihrem Kleiderschrank gibt es eine Menge von Tüchern, gibt es x Schubladen für jede Art von Kleidung, die Schubladen zu jedem anderen nächsten sind, die erste Schublade 1 Artikel hat, hat jede Schublade so viele Tücher als in der Schublade links und einem mehr, so dass Sie so etwas wie 1 Hut haben, 2 Perücken, .. (x-1) Hosen, dann x Shirts. Nun, wie viele Möglichkeiten können Sie ein einzelnes Element aus jeder Schublade mit verkleiden.

Hinweis: dieses Beispiel dar, wie viele Blätter in einem Entscheidungsbaum, wo number of children = depth, die durch 1 * 2 * 3 * .. * x erfolgt