Frage Was bedeutet O (log n) genau?


Ich lerne gerade über Laufzeiten und amortisierte Zeiten von Big O Notation. Ich verstehe die Vorstellung von Auf) lineare Zeit, was bedeutet, dass die Größe der Eingabe das Wachstum des Algorithmus proportional beeinflusst ... und dasselbe gilt beispielsweise für die quadratische Zeit Auf2) usw..alle Algorithmen, wie Permutationsgeneratoren, mit Auf!) Zeiten, die nach Faktoren wachsen.

Zum Beispiel ist die folgende Funktion Auf) weil der Algorithmus proportional zu seiner Eingabe wächst n:

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

Wenn es eine verschachtelte Schleife gäbe, wäre die Zeit ähnlich O (n2).

Aber was genau ist O (log n)? Zum Beispiel, was bedeutet es zu sagen, dass die Höhe eines vollständigen Binärbaums ist O (log n)?

Ich weiß (vielleicht nicht sehr detailliert), was Logarithmus ist, in dem Sinne: Log10 100 = 2, aber ich kann nicht verstehen, wie man eine Funktion mit einer logarithmischen Zeit identifiziert.


1732
2018-02-21 20:05


Ursprung


Antworten:


Ich kann nicht verstehen, wie man eine Funktion mit einer Protokollzeit identifiziert.

Die gebräuchlichsten Attribute der logarithmischen Laufzeitfunktion sind:

  • die Wahl des nächsten Elements, auf dem eine Aktion ausgeführt werden soll, ist eine von mehreren Möglichkeiten, und
  • nur einer muss ausgewählt werden.

oder

  • Die Elemente, auf denen die Aktion ausgeführt wird, sind Ziffern von n

Dies ist der Grund, warum zum Beispiel das Nachschlagen von Personen in einem Telefonbuch O (log n) ist. Sie müssen nicht überprüfen jeden Person im Telefonbuch, um die richtige zu finden; Stattdessen können Sie einfach "teilen und herrschen", indem Sie nach dem alphabetischen Namen suchen, und in jedem Abschnitt müssen Sie nur eine Teilmenge jedes Abschnitts erkunden, bevor Sie schließlich die Telefonnummer eines anderen finden.

Natürlich dauert ein größeres Telefonbuch immer noch länger, aber es wird nicht so schnell wachsen wie der proportionale Anstieg der zusätzlichen Größe.


Wir können das Telefonbuchbeispiel erweitern, um andere Arten von Operationen zu vergleichen und ihr Laufzeit. Wir werden davon ausgehen, dass unser Telefonbuch hat Unternehmen (die "Gelben Seiten"), die eindeutige Namen und haben Menschen (die "White Pages"), die möglicherweise keine eindeutigen Namen haben. Eine Telefonnummer wird höchstens einer Person oder einem Unternehmen zugewiesen. Wir nehmen auch an, dass es dauernd dauert, um auf eine bestimmte Seite zu wechseln.

Hier sind die Laufzeiten einiger Operationen, die wir im Telefonbuch durchführen können, von den besten zu den schlechtesten:

  • O (1) (bester Fall): Geben Sie die Telefonnummer ein, wenn die Seite, auf der sich der Name eines Unternehmens befindet, und der Firmenname angezeigt werden.

  • O (1) (Durchschnittsfall): Geben Sie auf der Seite, auf der sich der Name einer Person befindet, und nach ihrem Namen die Telefonnummer an.

  • O (log n): Wenn Sie den Namen einer Person angeben, suchen Sie nach der Telefonnummer, indem Sie einen zufälligen Punkt etwa auf halbem Weg durch den Teil des Buches auswählen, den Sie noch nicht durchsucht haben, und prüfen Sie dann, ob der Name der Person zu diesem Zeitpunkt ist. Dann wiederholen Sie den Vorgang etwa auf halbem Weg durch den Teil des Buches, in dem der Name der Person liegt. (Dies ist eine binäre Suche nach dem Namen einer Person.)

  • Auf): Finde alle Personen, deren Telefonnummern die Ziffer "5" enthalten.

  • Auf): Gib eine Telefonnummer an und finde die Person oder das Geschäft mit dieser Nummer.

  • O (n log n): Es gab eine Verwechslung in der Druckerei, und in unserem Telefonbuch wurden alle Seiten in zufälliger Reihenfolge eingefügt. Korrigieren Sie die Reihenfolge, so dass sie korrekt ist, indem Sie den Vornamen auf jeder Seite ansehen und diese Seite dann an der entsprechenden Stelle in ein neues, leeres Telefonbuch einfügen.

Für die folgenden Beispiele sind wir jetzt in der Druckerei. Telefonbücher warten darauf, an jeden Bewohner oder Geschäft geschickt zu werden, und es gibt einen Aufkleber auf jedem Telefonbuch, der angibt, wo es verschickt werden sollte. Jede Person oder jedes Unternehmen erhält ein Telefonbuch.

  • O (n log n): Wir möchten das Telefonbuch personalisieren, so dass wir den Namen jeder Person oder jedes Unternehmens in ihrer jeweiligen Kopie finden, dann ihren Namen in das Buch einkreisen und ein kurzes Dankschreiben für ihre Schirmherrschaft schreiben.

  • Auf2): Ein Fehler ist im Büro aufgetreten, und jeder Eintrag in jedem der Telefonbücher hat eine zusätzliche "0" am Ende der Telefonnummer. Nimm etwas White-out und entferne jede Null.

  • O (n · n!): Wir sind bereit, die Telefonbücher auf die Versandstation zu laden. Leider ist der Roboter, der die Bücher laden sollte, verrückt geworden: Er legt die Bücher in zufälliger Reihenfolge auf den LKW! Schlimmer noch, es lädt alle Bücher auf den LKW, prüft dann, ob sie in der richtigen Reihenfolge sind, und wenn nicht, entlädt es sie und beginnt von vorne. (Dies ist die gefürchtete Bogo sortieren.)

  • Aufn): Du reparierst den Roboter, damit er die Dinge richtig lädt. Am nächsten Tag spielt einer Ihrer Mitarbeiter einen Streich und verkabelt den Laderodroboter an die automatisierten Drucksysteme. Jedes Mal, wenn der Roboter ein Originalbuch lädt, nimmt der Fabrikdrucker alle Telefonbücher doppelt vor! Glücklicherweise sind die Fehlererkennungssysteme des Roboters hochentwickelt genug, dass der Roboter nicht versucht, noch mehr Kopien zu drucken, wenn er ein doppeltes Buch zum Laden findet, aber er muss immer noch jedes Original und doppelte Buch, das gedruckt wurde, laden.


2177
2018-02-21 20:14



Viele gute Antworten wurden bereits auf diese Frage geschrieben, aber ich glaube, dass wir wirklich eine wichtige Antwort verpassen - nämlich die bebilderte Antwort.

Was bedeutet es zu sagen, dass die Höhe eines vollständigen binären Baumes O (log n) ist?

Die folgende Zeichnung zeigt einen Binärbaum. Beachten Sie, dass jede Ebene die doppelte Anzahl an Knoten enthält, verglichen mit der darüber liegenden Ebene binär):

Binary tree

Binäre Suche ist ein Beispiel mit Komplexität O(log n). Nehmen wir an, dass die Knoten in der unteren Ebene des Baums in Abbildung 1 Elemente in einer sortierten Sammlung darstellen. Binäre Suche ist ein Divide-and-Conquer-Algorithmus, und die Zeichnung zeigt, wie wir (maximal) 4 Vergleiche benötigen, um den Datensatz zu finden, nach dem wir in diesem 16-Item-Datensatz suchen.

Angenommen, wir hätten stattdessen einen Datensatz mit 32 Elementen. Fahren Sie mit der obigen Zeichnung fort, um festzustellen, dass wir nun 5 Vergleiche benötigen, um zu finden, wonach wir suchen, da der Baum nur eine Stufe tiefer gewachsen ist, als wir die Datenmenge multipliziert haben. Infolgedessen kann die Komplexität des Algorithmus als eine logarithmische Ordnung beschrieben werden.

Plotten log(n) Auf einem einfachen Stück Papier ergibt sich ein Graph, in dem der Anstieg der Kurve sich verlangsamt n erhöht sich:

O(log n)


509
2018-02-21 22:22



O(log N) Grundsätzlich bedeutet die Zeit steigt linear während der n steigt exponentiell. Also, wenn es dauert 1 zweitens zu berechnen 10 Elemente, wird es dauern 2 Sekunden zu berechnen 100 Elemente, 3 Sekunden zu berechnen 1000 Elemente und so weiter.

Es ist O(log n) wenn wir die Art von Algorithmen z. B. binäre Suche teilen und überwinden. Ein anderes Beispiel ist die schnelle Sortierung, bei der wir jedes Mal das Array in zwei Teile aufteilen und jedes Mal, wenn es dauert O(N) Zeit, um ein Pivot-Element zu finden. Daher es N O(log N) 


463
2018-02-21 20:18



Die folgende Erklärung verwendet den Fall eines vollständig ausgewogen Binärbaum, um zu verstehen, wie wir die logarithmische Zeitkomplexität erhalten.

Binärer Baum ist ein Fall, in dem ein Problem der Größe n in ein Unterproblem der Größe n / 2 unterteilt wird, bis wir ein Problem der Größe 1 erreichen:

height of a binary tree

Und so erhalten Sie O (log n), was die Menge an Arbeit ist, die auf dem obigen Baum ausgeführt werden muss, um eine Lösung zu erreichen.

Ein üblicher Algorithmus mit der Zeitkomplexität O (log n) ist die binäre Suche, deren rekursive Beziehung T (n / 2) + O (1) ist, d. H. Auf jeder nachfolgenden Ebene des Baums teilen Sie das Problem in die Hälfte und führen eine konstante Menge zusätzlicher Arbeit aus.


196
2017-10-26 19:33



Wenn Sie eine Funktion haben, die Folgendes umfasst:

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.

Dann dauert es Protokoll2(n) Zeit. Das Große O-NotationDas bedeutet, dass die Beziehung für große n nur wahr sein muss und dass konstante Faktoren und kleinere Terme ignoriert werden können.


120
2018-02-21 20:11



Überblick

Andere haben gute Diagrammbeispiele gegeben, beispielsweise die Baumdiagramme. Ich habe keine einfachen Codebeispiele gesehen. Zusätzlich zu meiner Erklärung werde ich einige Algorithmen mit einfachen Druckanweisungen bereitstellen, um die Komplexität verschiedener Algorithmuskategorien zu veranschaulichen.

Zuerst sollten Sie eine allgemeine Vorstellung von Logarithmus haben, von dem Sie profitieren können https://en.wikipedia.org/wiki/Logarithmus . Naturwissenschaftliche Nutzung e und der natürliche Baumstamm. Ingenieurschüler werden log_10 (log base 10) verwenden und Informatiker werden log_2 (log base 2) sehr oft verwenden, da Computer binärbasiert sind. Manchmal werden Sie Abkürzungen von natürlichem Log sehen ln()Normalerweise lassen Ingenieure das _10 ab und benutzen es einfach log() und log_2 wird als abgekürzt lg(). Alle Arten von Logarithmen wachsen in ähnlicher Weise, deshalb teilen sie die gleiche Kategorie von log(n).

Wenn Sie sich die folgenden Codebeispiele ansehen, empfehle ich, O (1), dann O (n) und dann O (n ^ 2) zu betrachten. Wenn du mit denen gut bist, dann sieh dir die anderen an. Ich habe saubere Beispiele und Variationen hinzugefügt, um zu demonstrieren, wie subtile Änderungen immer noch zu derselben Kategorisierung führen können.

Sie können sich O (1), O (n), O (logn) usw. als Klassen oder Kategorien von Wachstum vorstellen. Einige Kategorien benötigen mehr Zeit als andere. Diese Kategorien helfen uns, die Leistung des Algorithmus zu bestimmen. Einige wachsen schneller, wenn die Eingabe n wächst. Die folgende Tabelle zeigt dieses Wachstum numerisch. In der Tabelle unten denken Sie an log (n) als die Obergrenze von log_2.

enter image description here

Simple Code Beispiele für verschiedene große O Kategorien:

O (1) - Konstante Zeit Beispiele:

  • Algorithmus 1:

Algorithmus 1 druckt hello einmal und es hängt nicht von n ab, also wird es immer in konstanter Zeit laufen, so ist es O(1).

print "hello";
  • Algorithmus 2:

Algorithmus 2 druckt hallo dreimal, aber es hängt nicht von einer Eingabegröße ab. Selbst wenn n wächst, druckt dieser Algorithmus immer nur dreimal hello. Das heißt, 3 ist eine Konstante, also ist dieser Algorithmus auch O(1).

print "hello";
print "hello";
print "hello";

O (log (n)) - Logarithmische Beispiele:

  • Algorithmus 3 - Dies verhält sich wie "log_2"

Algorithmus 3 demonstriert einen Algorithmus, der in log_2 (n) ausgeführt wird. Beachten Sie, dass die Nachoperation der for-Schleife den aktuellen Wert von i um 2 multipliziert i geht von 1 bis 2 zu 4 bis 8 zu 16 bis 32 ...

for(int i = 1; i <= n; i = i * 2)
  print "hello";
  • Algorithmus 4 - Dies verhält sich wie "log_3"

Algorithmus 4 demonstriert log_3. Beachten i geht von 1 bis 3 bis 9 bis 27 ...

for(int i = 1; i <= n; i = i * 3)
  print "hello";
  • Algorithmus 5 - Dies verhält sich wie "log_1.02"

Der Algorithmus 5 ist wichtig, da er zeigt, dass, solange die Zahl größer als 1 ist und das Ergebnis wiederholt mit sich selbst multipliziert wird, dass Sie einen logarithmischen Algorithmus betrachten.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O (n) - lineare Zeit Beispiele:

  • Algorithmus 6

Dieser Algorithmus ist einfach und druckt hallo n mal.

for(int i = 0; i < n; i++)
  print "hello";
  • Algorithmus 7

Dieser Algorithmus zeigt eine Variation an, wo er hallo n / 2 mal ausdruckt. n / 2 = 1/2 * n. Wir ignorieren die 1/2-Konstante und sehen, dass dieser Algorithmus O (n) ist.

for(int i = 0; i < n; i = i + 2)
  print "hello";

O (n * log (n)) - nlog (n) Beispiele:

  • Algorithmus 8

Betrachten Sie dies als eine Kombination von O(log(n)) und O(n). Die Verschachtelung der for-Schleifen hilft uns, die O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";
  • Algorithmus 9

Der Algorithmus 9 ist wie der Algorithmus 8, aber jede der Schleifen hat Variationen erlaubt, die immer noch zu dem Endergebnis führen O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O (n ^ 2) - n Quadrat Beispiele:

  • Algorithmus 10

O(n^2) wird einfach durch Verschachteln von Standard für Schleifen erhalten.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";
  • Algorithmus 11

Wie Algorithmus 10, aber mit einigen Variationen.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O (n ^ 3) - n gewürfelte Beispiele:

  • Algorithmus 12

Dies ist wie Algorithmus 10, aber mit 3 Schleifen anstelle von 2.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";
  • Algorithmus 13

Wie Algorithmus 12, aber mit einigen Variationen, die immer noch ergeben O(n^3).

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

Zusammenfassung

Die obigen Beispiele geben einige einfache Beispiele und Variationen, um zu zeigen, welche subtilen Änderungen eingeführt werden können, die die Analyse wirklich nicht verändern. Hoffentlich gibt es Ihnen genug Einblick.


107
2018-04-26 22:50



Logarithmische Laufzeit (O(log n)) bedeutet im Wesentlichen, dass die Laufzeit im Verhältnis zum Logarithmus der Eingabegröße - als Beispiel, wenn 10 Elemente höchstens eine gewisse Zeit benötigen x, und 100 Gegenstände brauchen höchstens 2xund 10.000 Artikel braucht es höchstens 4xdann sieht es aus wie O(log n) Zeit Komplexität.


84
2018-02-21 20:10



Der Logarithmus

Ok, versuchen wir zu verstehen, was ein Logarithmus eigentlich ist.

Stellen Sie sich vor, wir haben ein Seil und haben es an ein Pferd gebunden. Wenn das Seil direkt an das Pferd gebunden ist, ist die Kraft, die das Pferd (zB von einem Mann) wegziehen müsste, direkt 1.

Stellen Sie sich vor, das Seil ist um eine Stange geschlungen. Das Pferd, um wegzukommen, muss jetzt viel härter ziehen. Die Anzahl der Zeiten hängt von der Rauheit des Seils und der Größe der Stange ab, aber nehmen wir an, dass sich die Kraft um 10 erhöhen wird (wenn das Seil eine vollständige Drehung macht).

Wenn das Seil einmal geschlungen ist, muss das Pferd 10 Mal stärker ziehen. Wenn der Mensch sich entschließt, es dem Pferd wirklich schwer zu machen, kann er das Seil erneut um eine Stange schleifen und seine Stärke um weitere 10 erhöhen. Eine dritte Schleife wird die Stärke nochmals um das 10-fache erhöhen.

enter image description here

Wir können sehen, dass der Wert für jede Schleife um 10 erhöht wird. Die Anzahl der Umdrehungen, die benötigt werden, um eine beliebige Zahl zu erhalten, nennt man den Logarithmus der Zahl, dh wir brauchen 3 Beiträge, um deine Stärke 1000 mal zu multiplizieren, 6 Beiträge um deine Stärke zu multiplizieren 1.000.000.

3 ist der Logarithmus von 1.000 und 6 ist der Logarithmus von 1.000.000 (Basis 10).

Was bedeutet O (log n) eigentlich? 

In unserem obigen Beispiel ist unsere "Wachstumsrate" O (log n). Für jede zusätzliche Schlaufe beträgt die Kraft, die unser Seil bewältigen kann, 10 mal mehr:

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

Nun hat das obige Beispiel die Basis 10 verwendet, aber glücklicherweise ist die Basis des Protokolls unbedeutend, wenn wir über die große o-Notation sprechen.

Stellen wir uns nun vor, Sie versuchen eine Zahl zwischen 1-100 zu erraten.

Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!  

Jetzt haben Sie 7 Vermutungen gebraucht, um das richtig zu machen. Aber wie ist die Beziehung hier? Wie viele Gegenstände können Sie bei jeder weiteren Schätzung erraten?

Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024

Anhand des Graphen können wir sehen, dass, wenn wir eine binäre Suche verwenden, um eine Zahl zwischen 1-100 zu erraten, wird es uns brauchen maximal 7 Versuche. Wenn wir 128 Zahlen hätten, könnten wir auch die Zahl in 7 Versuchen schätzen, aber 129 Zahlen werden uns bringen maximal 8 Versuche (in Relationen zu Logarithmen, hier würden wir 7 Annahmen für einen 128 Wertebereich, 10 Annahmen für einen 1024 Wertebereich benötigen. 7 ist der Logarithmus von 128, 10 ist der Logarithmus von 1024 (Basis 2)).

Beachten Sie, dass ich "höchstens" fett geschrieben habe. Große o Notation bezieht sich immer auf den schlimmsten Fall. Wenn Sie Glück haben, können Sie die Zahl in einem Versuch erraten und so ist der beste Fall O (1), aber das ist eine andere Geschichte.

Wir können sehen, dass unser Datensatz bei jeder Schätzung schrumpft. Eine gute Faustregel, um festzustellen, ob ein Algorithmus eine logarithmische Zeit hat, ist   um zu sehen, ob der Datensatz nach jeder Iteration um eine bestimmte Reihenfolge schrumpft

Was ist mit O (n log n)?

Sie werden schließlich eine linararithmische Zeit finden O (n log (n) Algorithmus. Die obige Faustregel gilt wieder, aber dieses Mal muss die logarithmische Funktion n-mal laufen, z. Reduzieren der Größe einer Liste n mal, die in Algorithmen wie einem Mergesort auftritt.

Sie können leicht erkennen, ob die algorithmische Zeit n log n ist. Suchen Sie nach einer äußeren Schleife, die durch eine Liste (O (n)) iteriert. Dann schau, ob es eine innere Schleife gibt. Wenn die innere Schleife ist schneiden / reduzieren Die Datenmenge für jede Iteration, diese Schleife ist (O (log n)) und der Gesamtalgorithmus ist = O (n log n).

Disclaimer: Das Seil-Logarithmus-Beispiel wurde aus dem ausgezeichneten gegriffen Mathematians Delight Buch von W.Sawyer. 


55
2017-10-08 14:27