Was bedeutet O (log n) genau?

Ich lerne über Big O Notation-Laufzeiten und amortisierte Zeiten. Ich verstehe den Begriff der linearen Zeit O (n) , was bedeutet, dass die Größe der Eingabe das Wachstum des Algorithmus proportional beeinflusst ... und dasselbe gilt zum Beispiel für die quadratische Zeit O (n ² ) usw. Selbst Algorithmen B. Permutationsgeneratoren mit O (n!) - Zeiten, die um Fakultäten wachsen.

Die folgende Funktion ist beispielsweise O (n), da der Algorithmus proportional zu seiner Eingabe n wächst :

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

In ähnlicher Weise wäre die Zeit O (n ² ) , wenn es eine verschachtelte Schleife gäbe .

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

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

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

Die häufigsten Attribute der logarithmischen Laufzeitfunktion sind:

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

oder

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

Aus diesem Grund ist beispielsweise das Nachschlagen von Personen in einem Telefonbuch O (log n). Sie müssen nicht jede Person im Telefonbuch überprüfen , um die richtige zu finden. Stattdessen können Sie einfach teilen und erobern, indem Sie anhand des alphabetischen Namens suchen. In jedem Abschnitt müssen Sie nur eine Teilmenge jedes Abschnitts untersuchen, bevor Sie schließlich die Telefonnummer einer Person finden.

Natürlich dauert ein größeres Telefonbuch noch länger, aber es wächst nicht so schnell wie die proportionale Zunahme der zusätzlichen Größe.

Wir können das Telefonbuchbeispiel erweitern, um andere Arten von Vorgängen und deren Laufzeit zu vergleichen . Wir gehen davon aus, dass unser Telefonbuch Unternehmen (die "Gelben Seiten") mit eindeutigen Namen und Personen (die "Weißen Seiten") enthält, die möglicherweise keine eindeutigen Namen haben. Eine Telefonnummer ist höchstens einer Person oder einem Unternehmen zugeordnet. Wir gehen auch davon aus, dass das Umblättern zu einer bestimmten Seite konstant dauert.

Hier sind die Laufzeiten einiger Vorgänge, die wir möglicherweise im Telefonbuch ausführen, vom schnellsten zum langsamsten:

• O (1) (im schlimmsten Fall): Suchen Sie anhand der Seite, auf der sich der Name eines Unternehmens befindet, und des Unternehmensnamens die Telefonnummer.

• O (1) (im Durchschnitt): Suchen Sie anhand der Seite, auf der sich der Name einer Person befindet, und ihres Namens die Telefonnummer.

• O (log n): Suchen Sie anhand des Namens einer Person die Telefonnummer, indem Sie einen zufälligen Punkt etwa in der Mitte des Teils des Buches auswählen, den Sie noch nicht durchsucht haben, und dann überprüfen, ob der Name der Person an diesem Punkt steht. Wiederholen Sie den Vorgang etwa zur Hälfte des Teils des Buches, in dem der Name der Person liegt. (Dies ist eine binäre Suche nach dem Namen einer Person.)

• O (n): Finde alle Personen, deren Telefonnummern die Ziffer "5" enthalten.

• O (n): Suchen Sie unter Angabe einer Telefonnummer die Person oder das Unternehmen mit dieser Nummer.

• O (n log n): Im Büro des Druckers gab es eine Verwechslung, und in unser 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 anzeigen und diese Seite dann an der entsprechenden Stelle in einem neuen, leeren Telefonbuch platzieren.

Für die folgenden Beispiele sind wir jetzt im Büro des Druckers. Telefonbücher warten darauf, an jeden Einwohner oder jedes Unternehmen gesendet zu werden, und auf jedem Telefonbuch befindet sich ein Aufkleber, auf dem angegeben ist, wohin es gesendet werden soll. Jede Person oder jedes Unternehmen erhält ein Telefonbuch.

• O (n log n): Wir möchten das Telefonbuch personalisieren, daher finden wir den Namen jeder Person oder jedes Unternehmens in der angegebenen Kopie, kreisen dann ihren Namen im Buch ein und schreiben einen kurzen Dankesbrief für ihre Schirmherrschaft .

• O (n ² ): Im Büro ist ein Fehler aufgetreten, und jeder Eintrag in jedem der Telefonbücher hat eine zusätzliche "0" am Ende der Telefonnummer. Nehmen Sie etwas White-Out und entfernen Sie jede Null.

• O (n · n!): Wir sind bereit, die Telefonbücher auf das Versanddock zu laden. Leider ist der Roboter, der die Bücher laden sollte, durcheinander geraten: 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-Sorte .)

• O (n ⁿ ): Sie reparieren den Roboter so, dass er die Dinge richtig lädt. Am nächsten Tag spielt Ihnen einer Ihrer Mitarbeiter einen Streich und verkabelt den Ladedockroboter mit den automatisierten Drucksystemen. Jedes Mal, wenn der Roboter ein Originalbuch lädt, führt der Werksdrucker eine doppelte Ausführung aller Telefonbücher durch! Glücklicherweise sind die Fehlererkennungssysteme des Roboters so ausgefeilt, dass der Roboter nicht versucht, noch mehr Kopien zu drucken, wenn er zum Laden auf ein doppeltes Buch stößt, aber dennoch jedes Original und jedes doppelte Buch laden muss, das gedruckt wurde.

O(log N)bedeutet im Grunde, dass die Zeit linear ansteigt, während die nexponentiell ansteigt. Wenn das 1Berechnen von 10Elementen 2Sekunden dauert, dauert das Berechnen von Elementen Sekunden, das Berechnen von 100Elementen 3Sekunden 1000und so weiter.

Es ist, O(log n)wenn wir Algorithmen teilen und erobern, z. B. binäre Suche. Ein weiteres Beispiel ist die schnelle Sortierung, bei der jedes Mal, wenn wir das Array in zwei Teile teilen und jedes Mal Zeit benötigt O(N)wird, um ein Pivot-Element zu finden. Daher es N O(log N)

Auf diese Frage wurden bereits viele gute Antworten veröffentlicht, aber ich glaube, wir vermissen wirklich eine wichtige - nämlich die illustrierte Antwort.

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

Die folgende Zeichnung zeigt einen Binärbaum. Beachten Sie, dass jede Ebene doppelt so viele Knoten enthält wie die obige Ebene (daher binär ):

Die binäre Suche ist ein Beispiel mit Komplexität O(log n). Angenommen, die Knoten in der unteren Ebene des Baums in Abbildung 1 repräsentieren Elemente in einer sortierten Sammlung. Die binäre Suche ist ein Divide-and-Conquer-Algorithmus. Die Zeichnung zeigt, wie wir (höchstens) 4 Vergleiche benötigen, um den Datensatz zu finden, nach dem wir in diesem Datensatz mit 16 Elementen suchen.

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

Das Zeichnen log(n)auf einem einfachen Blatt Papier führt zu einem Diagramm, in dem sich der Anstieg der Kurve mit nzunehmender Geschwindigkeit verlangsamt :

In der folgenden Erklärung wird der Fall eines vollständig ausgeglichenen Binärbaums verwendet, um Ihnen zu helfen, zu verstehen, wie wir die logarithmische Zeitkomplexität erhalten.

Binärbaum 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:

Und so erhalten Sie O (log n). Dies ist der Arbeitsaufwand, der für den obigen Baum ausgeführt werden muss, um eine Lösung zu finden.

Ein üblicher Algorithmus mit O (log n) -Zeitkomplexität ist die binäre Suche, deren rekursive Beziehung T (n / 2) + O (1) ist, dh auf jeder nachfolgenden Ebene des Baums teilen Sie das Problem in zwei Hälften und erledigen konstant zusätzliche Arbeit.

Überblick

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

Zunächst möchten Sie eine allgemeine Vorstellung vom Logarithmus haben, die Sie unter https://en.wikipedia.org/wiki/Logarithm erhalten . Naturwissenschaftliche Nutzung eund das natürliche Protokoll. Technische Schüler verwenden log_10 (log base 10) und Informatiker verwenden log_2 (log base 2) häufig, da Computer binär basieren. Manchmal werden Abkürzungen für natürliches Protokoll ln()angezeigt, da Ingenieure normalerweise die _10 weglassen und nur verwenden log()und log_2 als abgekürzt wird lg(). Alle Arten von Logarithmen wachsen auf ähnliche Weise, weshalb sie dieselbe Kategorie von Logarithmen haben log(n).

Wenn Sie sich die folgenden Codebeispiele ansehen, empfehle ich, sich O (1), dann O (n) und dann O (n ^ 2) anzusehen. Nachdem Sie mit diesen gut sind, schauen Sie sich die anderen an. Ich habe saubere Beispiele sowie Variationen beigefü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 des Wachstums vorstellen. Einige Kategorien benötigen mehr Zeit als andere. Diese Kategorien geben uns eine Möglichkeit, die Leistung des Algorithmus zu ordnen. Einige sind schneller gewachsen, wenn die Eingabe n wächst. Die folgende Tabelle zeigt das Wachstum numerisch. Stellen Sie sich in der folgenden Tabelle log (n) als die Obergrenze von log_2 vor.

Einfache Codebeispiele für verschiedene Big O-Kategorien:

O (1) - Beispiele für konstante Zeit:

• Algorithmus 1:

Algorithmus 1 druckt Hallo einmal und es hängt nicht von n ab, so dass es immer in konstanter Zeit ausgeführt wird, so ist es O(1).

print "hello";

• Algorithmus 2:

Algorithmus 2 gibt dreimal Hallo aus, hängt jedoch nicht von der Eingabegröße ab. Selbst wenn n wächst, druckt dieser Algorithmus immer nur dreimal Hallo. Davon abgesehen ist 3 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 zeigt einen Algorithmus, der in log_2 (n) ausgeführt wird. Beachten Sie, dass die Nachoperation der for-Schleife den aktuellen Wert von i mit 2 multipliziert, also ivon 1 nach 2 nach 4 nach 8 nach 16 nach 32 geht ...

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. Hinweis igeht 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"

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

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

O (n) - Beispiele für lineare Zeit:

• Algorithmus 6

Dieser Algorithmus ist einfach und druckt n-mal.

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

• Algorithmus 7

Dieser Algorithmus zeigt eine Variation, bei der n / 2 Mal Hallo gedruckt wird. 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

Stellen Sie sich dies als eine Kombination von O(log(n))und vor O(n). Das Verschachteln der for-Schleifen hilft uns, die zu erhaltenO(n*log(n))

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

• Algorithmus 9

Algorithmus 9 ist wie Algorithmus 8, aber jede der Schleifen hat Variationen zugelassen, die immer noch zum 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 im Quadrat Beispiele:

• Algorithmus 10

O(n^2) wird leicht durch Verschachtelungsstandard 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, jedoch 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ürfelt Beispiele:

• Algorithmus 12

Dies ist wie bei Algorithmus 10, jedoch 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, jedoch 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 enthalten einige einfache Beispiele und Variationen, um zu demonstrieren, welche subtilen Änderungen eingeführt werden können, die die Analyse wirklich nicht ändern. Hoffentlich gibt es Ihnen genug Einblick.

Wenn Sie eine Funktion hatten, die Folgendes übernimmt:

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 log ₂ (n) Zeit. Die Big O-Notation bedeutet lose gesagt, dass die Beziehung nur für großes n wahr sein muss und dass konstante Faktoren und kleinere Terme ignoriert werden können.

Logarithmische Laufzeit ( O(log n)) bedeutet im Wesentlichen, dass die Laufzeit proportional zum Logarithmus der Eingabegröße wächst - zum Beispiel, wenn 10 Elemente höchstens einige Zeit xund beispielsweise 100 Elemente höchstens 2x10.000 Elemente benötigen dauert höchstens 4x, dann sieht es aus wie eine O(log n)zeitliche Komplexität.

Der Logarithmus

Ok, lassen Sie uns versuchen, vollständig zu verstehen, was ein Logarithmus eigentlich ist.

Stellen Sie sich vor, wir haben ein Seil und wir haben es an ein Pferd gebunden. Wenn das Seil direkt an das Pferd gebunden ist, beträgt die Kraft, die das Pferd abziehen müsste (z. B. von einem Mann), direkt 1.

Stellen Sie sich nun vor, das Seil ist um eine Stange geschlungen. Das Pferd, um wegzukommen, muss jetzt um ein Vielfaches stärker ziehen. Die Häufigkeit hängt von der Rauheit des Seils und der Größe der Stange ab. Nehmen wir jedoch an, dass die eigene Stärke mit 10 multipliziert wird (wenn das Seil eine vollständige Drehung ausführt).

Wenn das Seil einmal geschlungen ist, muss das Pferd zehnmal stärker ziehen. Wenn der Mensch beschließt, es dem Pferd wirklich schwer zu machen, kann er das Seil erneut um eine Stange legen und seine Stärke um weitere 10-mal erhöhen. Eine dritte Schleife erhöht die Stärke erneut um das Zehnfache.

Wir können sehen, dass sich der Wert für jede Schleife um 10 erhöht. Die Anzahl der Umdrehungen, die erforderlich sind, um eine beliebige Zahl zu erhalten, wird als Logarithmus der Zahl bezeichnet, dh wir benötigen 3 Pfosten, um Ihre Stärke um das 1000-fache zu multiplizieren, 6 Pfosten, um Ihre Stärke mit 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 weitere Schlaufe beträgt die Kraft, mit der unser Seil umgehen kann, das Zehnfache:

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

Im obigen Beispiel wurde die Basis 10 verwendet, aber zum Glück ist die Basis des Protokolls unbedeutend, wenn wir über die Big-O-Notation sprechen.

Stellen wir uns nun vor, Sie versuchen, eine Zahl zwischen 1 und 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 angestellt, um dies richtig zu machen. Aber wie ist die Beziehung hier? Was ist die größte Anzahl von Gegenständen, die Sie aus jeder weiteren Vermutung erraten können?

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

Anhand des Diagramms können wir sehen, dass wir höchstens 7 Versuche benötigen, wenn wir eine binäre Suche verwenden, um eine Zahl zwischen 1 und 100 zu erraten . Wenn wir 128 Zahlen hätten, könnten wir die Zahl auch in 7 Versuchen erraten, aber 129 Zahlen benötigen höchstens 8 Versuche (in Bezug auf Logarithmen würden wir hier 7 Vermutungen für einen 128-Wertebereich, 10 Vermutungen 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 gedruckt habe. Die Big-O-Notation bezieht sich immer auf den schlimmsten Fall. Wenn Sie Glück haben, können Sie die Zahl in einem Versuch erraten. Der beste Fall ist also O (1), aber das ist eine andere Geschichte.

Wir können sehen, dass unser Datensatz bei jeder Vermutung schrumpft. Eine gute Faustregel, um festzustellen, ob ein Algorithmus eine logarithmische Zeit hat, besteht darin, zu prüfen, ob der Datensatz nach jeder Iteration um eine bestimmte Reihenfolge verkleinert wird

Was ist mit O (n log n)?

Sie werden schließlich auf einen linearithmischen Zeit- O- Algorithmus (n log (n)) stoßen . Die obige Faustregel gilt erneut, aber dieses Mal muss die logarithmische Funktion n-mal ausgeführt werden, z. B. die Größe einer Liste n-mal reduzieren , was bei Algorithmen wie einem Mergesort der Fall ist.

Sie können leicht erkennen, ob die algorithmische Zeit n log n ist. Suchen Sie nach einer äußeren Schleife, die eine Liste durchläuft (O (n)). Überprüfen Sie dann, ob eine innere Schleife vorhanden ist. Wenn die innere Schleife den Datensatz bei jeder Iteration schneidet / reduziert , ist diese Schleife (O (log n)), und daher ist der Gesamtalgorithmus = O (n log n) .

Haftungsausschluss: Das Beispiel für den Seillogarithmus stammt aus dem hervorragenden Buch Mathematician's Delight von W.Sawyer .

Sie können sich O (log N) intuitiv vorstellen, indem Sie sagen, dass die Zeit proportional zur Anzahl der Stellen in N ist.

Wenn eine Operation eine konstante Zeitarbeit für jede Ziffer oder jedes Bit einer Eingabe ausführt, benötigt die gesamte Operation Zeit proportional zur Anzahl der Ziffern oder Bits in der Eingabe, nicht zur Größe der Eingabe. also O (log N) anstelle von O (N).

Wenn eine Operation eine Reihe konstanter Zeitentscheidungen trifft, von denen jede die Größe der zu berücksichtigenden Eingabe halbiert (um den Faktor 3, 4, 5 ... verringert), benötigt das Ganze Zeit proportional zur logarithmischen Basis 2 (Basis 3) , Basis 4, Basis 5 ...) der Größe N der Eingabe, anstatt O (N) zu sein.

Und so weiter.

Ich musste einen Algorithmus, der in O (log n) ausgeführt wird, immer am besten mental visualisieren:

Wenn Sie die Problemgröße um einen multiplikativen Betrag erhöhen (dh ihre Größe mit 10 multiplizieren), wird die Arbeit nur um einen additiven Betrag erhöht.

Wenn Sie dies auf Ihre Frage zum Binärbaum anwenden, haben Sie eine gute Anwendung: Wenn Sie die Anzahl der Knoten in einem Binärbaum verdoppeln, erhöht sich die Höhe nur um 1 (eine additive Menge). Wenn Sie es noch einmal verdoppeln, erhöht es sich immer noch nur um 1. (Natürlich gehe ich davon aus, dass es ausgeglichen bleibt und so). Auf diese Weise erledigen Sie Ihre Arbeit nicht nur, wenn sich die Problemgröße vervielfacht, sondern nur geringfügig mehr. Deshalb sind O (log n) -Algorithmen fantastisch.

Zuerst empfehle ich Ihnen, folgendes Buch zu lesen;

Algorithmen (4. Auflage)

Hier sind einige Funktionen und ihre erwarteten Komplexitäten. Zahlen geben die Häufigkeit der Anweisungsausführung an .

Das folgende Big-O-Komplexitätsdiagramm stammt ebenfalls aus dem Bigocheatsheet

Schließlich gibt es ein sehr einfaches Schaufenster, das zeigt, wie es berechnet wird;

Anatomie der Häufigkeit der Ausführung von Anweisungen eines Programms.

Analyse der Laufzeit eines Programms (Beispiel).

Was ist log _b (n)?

Dies ist die Häufigkeit, mit der Sie ein Protokoll der Länge n wiederholt in b gleiche Teile schneiden können, bevor Sie einen Abschnitt der Größe 1 erreichen.

Divide- und Conquer-Algorithmen haben normalerweise eine lognKomponente zur Laufzeit. Dies ergibt sich aus der wiederholten Halbierung der Eingabe.

Bei der binären Suche wird bei jeder Iteration die Hälfte der Eingabe weggeworfen. Es ist zu beachten, dass in der Big-O-Notation log log base 2 ist.

Bearbeiten: Wie bereits erwähnt, spielt die Protokollbasis keine Rolle, aber wenn die Big-O-Leistung eines Algorithmus abgeleitet wird, ergibt sich der Protokollfaktor aus der Halbierung, weshalb ich ihn als Basis 2 betrachte.

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

Ich würde dies umformulieren als 'Höhe eines vollständigen Binärbaums ist log n'. Das Ermitteln der Höhe eines vollständigen Binärbaums wäre O (log n), wenn Sie Schritt für Schritt nach unten gehen würden.

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

Der Logarithmus ist im Wesentlichen die Umkehrung der Potenzierung. Wenn also jeder 'Schritt' Ihrer Funktion einen Faktor eliminiert aus dem ursprünglichen Objektsatz entfernt, ist dies ein logarithmischer Zeitalgorithmus.

Im Baumbeispiel können Sie leicht erkennen, dass das Herabsetzen einer Knotenebene eine exponentielle Anzahl von Elementen verringert, wenn Sie weiter durchlaufen. Das beliebte Beispiel für das Durchsuchen eines nach Namen sortierten Telefonbuchs entspricht im Wesentlichen dem Durchsuchen eines binären Suchbaums (die mittlere Seite ist das Stammelement, und Sie können bei jedem Schritt ableiten, ob Sie nach links oder rechts gehen möchten).

Diese beiden Fälle benötigen O (log n) Zeit

case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }


 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }

O (log n) ist etwas irreführend, genauer gesagt O (log ₂₎ n), dh (Logarithmus mit Basis 2).

Die Höhe eines ausgeglichenen Binärbaums ist O (log ₂ n), da jeder Knoten zwei untergeordnete Knoten hat (beachten Sie die "zwei" wie in log ₂ n). Ein Baum mit n Knoten hat also eine Höhe von log ₂ n.

Ein weiteres Beispiel ist die binäre Suche mit einer Laufzeit von O (log ₂ n), da Sie bei jedem Schritt den Suchraum durch 2 teilen.

O(log n) bezieht sich auf eine Funktion (oder einen Algorithmus oder einen Schritt in einem Algorithmus), die in einer Zeit arbeitet, die proportional zum Logarithmus ist (normalerweise Basis 2 in den meisten Fällen, aber nicht immer, und in jedem Fall ist dies durch die Big-O-Notation * unbedeutend). der Größe der Eingabe.

Die logarithmische Funktion ist die Umkehrung der Exponentialfunktion. Anders ausgedrückt: Wenn Ihre Eingabe exponentiell wächst (und nicht linear, wie Sie es normalerweise betrachten würden), wächst Ihre Funktion linear.

O(log n)Laufzeiten sind bei jeder Art von Divide-and-Conquer-Anwendung sehr häufig, da Sie die Arbeit (idealerweise) jedes Mal halbieren. Wenn Sie in jedem der Divisions- oder Eroberungsschritte konstante Zeitarbeit leisten (oder Arbeit, die nicht zeitkonstant ist, sondern mit langsamerer Zeit als O(log n)), dann ist Ihre gesamte Funktion O(log n). Es ist ziemlich üblich, dass jeder Schritt stattdessen eine lineare Zeit für die Eingabe erfordert. Dies entspricht einer Gesamtzeitkomplexität vonO(n log n) .

Die Laufzeitkomplexität der binären Suche ist ein Beispiel dafür O(log n) . Dies liegt daran, dass Sie bei der binären Suche in jedem späteren Schritt immer die Hälfte Ihrer Eingabe ignorieren, indem Sie das Array in zwei Hälften teilen und sich bei jedem Schritt nur auf eine Hälfte konzentrieren. Jeder Schritt ist zeitkonstant, da Sie bei der binären Suche nur ein Element mit Ihrem Schlüssel vergleichen müssen, um herauszufinden, was als Nächstes zu tun ist, unabhängig davon, wie groß das Array ist, das Sie in Betracht ziehen. Sie führen also ungefähr log (n) / log (2) Schritte aus.

Die Laufzeitkomplexität der Zusammenführungssortierung ist ein Beispiel dafür O(n log n). Dies liegt daran, dass Sie das Array bei jedem Schritt in zwei Hälften teilen, was insgesamt ungefähr log (n) / log (2) Schritte ergibt. In jedem Schritt müssen Sie jedoch Zusammenführungsoperationen für alle Elemente ausführen (ob es sich um eine Zusammenführungsoperation für zwei Unterlisten von n / 2 Elementen oder zwei Zusammenführungsoperationen für vier Unterlisten von n / 4 Elementen handelt, ist irrelevant, da dies zu einer Notwendigkeit beiträgt Tun Sie dies für n Elemente in jedem Schritt. Somit ist die Gesamtkomplexität O(n log n).

* Denken Sie daran, dass Konstanten in der Big-O-Notation per Definition keine Rolle spielen. Auch durch die Änderung der Basisregel für Logarithmen ist der einzige Unterschied zwischen Logarithmen verschiedener Basen ein konstanter Faktor.

Dies bedeutet einfach, dass die für diese Aufgabe benötigte Zeit mit log (n) zunimmt (Beispiel: 2s für n = 10, 4s für n = 100, ...). Weitere Informationen finden Sie in den Wikipedia-Artikeln zum binären Suchalgorithmus und zur Big O-Notation .

Einfach ausgedrückt: Bei jedem Schritt Ihres Algorithmus können Sie die Arbeit halbieren. (Asymptotisch äquivalent zu drittem, viertem, ...)

Wenn Sie eine logarithmische Funktion auf einem Grafikrechner oder ähnlichem darstellen, werden Sie feststellen, dass sie sehr langsam ansteigt - sogar langsamer als eine lineare Funktion.

Aus diesem Grund sind Algorithmen mit einer logarithmischen Zeitkomplexität sehr gefragt: Selbst für wirklich große n (sagen wir zum Beispiel n = 10 ^ 8) sind sie mehr als akzeptabel.

Aber was genau ist O (log n)

Was es genau bedeutet, ist "wie ntendenziell infinity, wo timetendenziell ein konstanter Skalierungsfaktor ist".a*log(n)a

Oder eigentlich heißt das nicht ganz so; wahrscheinlicher bedeutet es so etwas wie " timegeteilt durch a*log(n)Tendenzen zu 1".

"Neigt zu" hat die übliche mathematische Bedeutung von "Analyse": Zum Beispiel: "Wenn Sie eine beliebig kleine Konstante ungleich Null auswählen k, kann ich einen entsprechenden Wert finden X, der ((time/(a*log(n))) - 1)kleiner ist als kfür alle Werte ngrößer als X."

In Laienform bedeutet dies, dass die Zeitgleichung einige andere Komponenten haben kann: z. B. kann sie eine konstante Startzeit haben; Diese anderen Komponenten verblassen jedoch in Richtung Bedeutungslosigkeit für große Werte von n, und a * log (n) ist der dominierende Ausdruck für großes n.

Beachten Sie, dass wenn die Gleichung zum Beispiel ...

Zeit (n) = a + b log (n) + c n + d n n

... dann wäre dies O (n im Quadrat), denn unabhängig von den Werten der Konstanten a, b, c und ungleich Null d d*n*nwürde der Term für jeden ausreichend großen Wert von n immer über den anderen dominieren.

Das ist, was Bit-O-Notation bedeutet: Es bedeutet "Was ist die Reihenfolge des dominanten Terms für ein ausreichend großes n".

Ich kann etwas Interessantes hinzufügen, das ich vor langer Zeit in einem Buch von Kormen usw. gelesen habe. Stellen Sie sich nun ein Problem vor, bei dem wir in einem Problemraum eine Lösung finden müssen. Dieser Problemraum sollte endlich sein.

Wenn Sie nun nachweisen können, dass Sie bei jeder Iteration Ihres Algorithmus einen Bruchteil dieses Speicherplatzes abschneiden, der nicht unter einer bestimmten Grenze liegt, bedeutet dies, dass Ihr Algorithmus in O (logN) -Zeit ausgeführt wird.

Ich möchte darauf hinweisen, dass es sich hier um eine relative Bruchgrenze handelt, nicht um die absolute. Die binäre Suche ist ein klassisches Beispiel. Bei jedem Schritt werfen wir die Hälfte des Problemraums weg. Die binäre Suche ist jedoch nicht das einzige Beispiel dafür. Angenommen, Sie haben irgendwie bewiesen, dass Sie bei jedem Schritt mindestens 1/128 des Problemraums wegwerfen. Das bedeutet, dass Ihr Programm immer noch zur Zeit O (logN) ausgeführt wird, obwohl es erheblich langsamer ist als die binäre Suche. Dies ist ein sehr guter Hinweis bei der Analyse rekursiver Algorithmen. Es kann oft bewiesen werden, dass bei der Rekursion bei jedem Schritt nicht mehrere Varianten verwendet werden, und dies führt dazu, dass ein Bruchteil des Problemraums abgeschnitten wird.

Ich kann ein Beispiel für eine for-Schleife geben und vielleicht ist das Konzept in verschiedenen Kontexten einfacher zu verstehen, wenn ich es einmal verstanden habe.

Das bedeutet, dass der Schritt in der Schleife exponentiell wächst. Z.B

for (i=1; i<=n; i=i*2) {;}

Die Komplexität in der O-Notation dieses Programms ist O (log (n)). Versuchen wir, es von Hand zu durchlaufen (n liegt irgendwo zwischen 512 und 1023 (außer 1024):

step: 1   2   3   4   5    6    7    8     9     10
   i: 1   2   4   8   16   32   64   128   256   512

Obwohl n irgendwo zwischen 512 und 1023 liegt, finden nur 10 Iterationen statt. Dies liegt daran, dass der Schritt in der Schleife exponentiell wächst und daher nur 10 Iterationen benötigt, um die Beendigung zu erreichen.

Der Logarithmus von x (zur Basis von a) ist die Umkehrfunktion von a ^ x.

Es ist wie zu sagen, dass der Logarithmus die Umkehrung des Exponentials ist.

Versuchen Sie nun, es so zu sehen: Wenn das Exponential sehr schnell wächst, wächst der Logarithmus (umgekehrt) sehr langsam.

Der Unterschied zwischen O (n) und O (log (n)) ist groß, ähnlich dem Unterschied zwischen O (n) und O (a ^ n) (a ist eine Konstante).

Wenn Sie eine Liste mit n Elementen haben und aus dieser Liste einen Binärbaum erstellen (wie im Divide and Conquer-Algorithmus), teilen Sie durch 2, bis Sie Listen der Größe 1 (die Blätter) erreichen.

Im ersten Schritt teilen Sie durch 2. Sie haben dann 2 Listen (2 ^ 1), Sie teilen jede durch 2, Sie haben also 4 Listen (2 ^ 2), Sie teilen erneut, Sie haben 8 Listen (2 ^ 3) ) und so weiter, bis Ihre Listengröße 1 ist

Das gibt Ihnen die Gleichung:

n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps

(Sie nehmen das lg jeder Seite, wobei lg die logarithmische Basis 2 ist)

Jedes Mal, wenn wir einen Algorithmus oder Code schreiben, versuchen wir, seine asymptotische Komplexität zu analysieren. Es unterscheidet sich von seiner zeitlichen Komplexität .

Asymptotische Komplexität ist das Verhalten der Ausführungszeit eines Algorithmus, während die Zeitkomplexität die tatsächliche Ausführungszeit ist. Einige Leute verwenden diese Begriffe jedoch synonym.

Weil die zeitliche Komplexität von verschiedenen Parametern abhängt, nämlich.
1. Physikalisches System
2. Programmiersprache
3. Codierungsstil
4. Und vieles mehr ......

Die tatsächliche Ausführungszeit ist kein gutes Maß für die Analyse.

Stattdessen nehmen wir die Eingabegröße als Parameter, da die Eingabe unabhängig vom Code dieselbe ist. Die Ausführungszeit ist also eine Funktion der Eingabegröße.

Es folgt ein Beispiel für einen linearen Zeitalgorithmus

Lineare Suche
Bei n Eingabeelementen benötigen Sie höchstens 'n' Vergleiche , um ein Element im Array zu suchen . Mit anderen Worten, egal welche Programmiersprache Sie verwenden, welchen Codierungsstil Sie bevorzugen, auf welchem ​​System Sie sie ausführen. Im schlimmsten Fall sind nur n Vergleiche erforderlich. Die Ausführungszeit ist linear proportional zur Eingabegröße.

Und es ist nicht nur eine Suche, was auch immer die Arbeit sein mag (Inkrementieren, Vergleichen oder irgendeine Operation), es ist eine Funktion der Eingabegröße.

Wenn Sie also sagen, dass ein Algorithmus O (log n) ist, bedeutet dies, dass die Ausführungszeit log mal die Eingabegröße n ist.

Mit zunehmender Eingabegröße nimmt die geleistete Arbeit (hier die Ausführungszeit) zu. (Daher Proportionalität)

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

Wenn die Eingabegröße zunimmt, nimmt die geleistete Arbeit zu und ist unabhängig von jeder Maschine. Und wenn Sie versuchen, den Wert von Arbeitseinheiten herauszufinden, hängt dies tatsächlich von den oben angegebenen Parametern ab. Dies ändert sich je nach System und allen.

log x to base b = y ist die Umkehrung von b^y = x

Wenn Sie einen M-Baum mit der Tiefe d und der Größe n haben, dann:

• Durchqueren des gesamten Baumes ~ O (M ^ d) = O (n)

• Einen einzelnen Weg im Baum gehen ~ O (d) = O (log n zur Basis M)

In der Informationstechnologie bedeutet dies:

  f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, 
  such that
  for all N>N0  "C*g(n) > f(n) > 0" is true.

Ameise scheint es, dass diese Notation größtenteils aus der Mathematik stammt.

In diesem Artikel gibt es ein Zitat: DE Knuth, "BIG OMICRON UND BIG OMEGA UND BIG THETA", 1976 :

Auf der Grundlage der hier diskutierten Themen schlage ich vor, dass Mitglieder von SIGACT und Herausgeber von Fachzeitschriften für Informatik und Mathematik Notationen wie oben definiert annehmen, es sei denn, eine bessere Alternative kann relativ bald gefunden werden .

Heute ist 2016, aber wir nutzen es noch heute.

In der mathematischen Analyse bedeutet dies:

  lim (f(n)/g(n))=Constant; where n goes to +infinity

Aber selbst in der mathematischen Analyse wurde dieses Symbol manchmal verwendet, um "C * g (n)> f (n)> 0" zu bedeuten.

Wie ich von der Universität weiß, wurde das Symbol vom deutschen Mathematiker Landau (1877-1938) eingeführt.

Das vollständige binäre Beispiel ist O (ln n), da die Suche folgendermaßen aussieht:

1 2 3 4 5 6 7 8 9 10 11 12

Die Suche nach 4 ergibt 3 Treffer: 6, 3, dann 4. Und log2 12 = 3, was ungefähr der Anzahl der erforderlichen Treffer entspricht.

Wenn Sie nach einer auf Intuition basierenden Antwort suchen, möchte ich zwei Interpretationen für Sie aufstellen.

1. Stellen Sie sich einen sehr hohen Hügel mit einer sehr breiten Basis vor. Um die Spitze des Hügels zu erreichen, gibt es zwei Möglichkeiten: Eine ist ein spezieller Weg, der spiralförmig um den Hügel herum führt und die andere führt: eine kleine Terrasse wie Schnitzereien, die als Treppe ausgeschnitten sind. Wenn nun der erste Weg in der linearen Zeit O (n) erreicht, ist der zweite Weg O (log n).

2. Stellen Sie sich einen Algorithmus vor, der eine ganze Zahl nals Eingabe akzeptiert und zeitlich proportional zu nO (n) oder Theta (n) abschließt. Wenn er jedoch zeitlich proportional zu ausgeführt wird, number of digits or the number of bits in the binary representation on numberläuft der Algorithmus in O (log n) oder Theta (log n) Zeit.

Algorithmen im Divide and Conquer-Paradigma sind von Komplexität O (logn). Ein Beispiel hier, berechnen Sie Ihre eigene Potenzfunktion,

int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

von http://www.geeksforgeeks.org/write-ac-program-to-calculate-powxn/