Algorithmische Intuition für logarithmische Komplexität

59

Ich glaube, ich habe ein vernünftiges Verständnis für Komplexitäten wie , Θ ( n ) und Θ ( n 2 ) .O(1)Θ(n)Θ(n2)

In Bezug auf eine Liste ist eine konstante Suche, sodass es nur den Kopf der Liste erhält. Θ ( n ) ist die Stelle, an der ich die gesamte Liste durchlaufen würde, und Θ ( n 2 ) durchläuft die Liste für jedes Element in der Liste einmal.O(1)Θ(n)Θ(n2)

Gibt es eine ähnliche intuitive Möglichkeit, zu erfassen, außer zu wissen, dass es irgendwo zwischen O ( 1 ) und Θ ( n ) liegt ?Θ(logn)O(1)Θ(n)

Khanzor
quelle
8
log n ist für "Suche": denke, binäre Suche
Suresh
2
Die Verwendung von zum Stellen dieser Frage ist falsch, da es nur eine obere Schranke angibt. Zum Beispiel ist die konstante Zeit O ( log n ) . θ wäre geeigneter. Siehe Meta-Frage: meta.cs.stackexchange.com/questions/182/…OO(logn)θ
Aryabhata
1
Weitere Informationen zu SO: Was bedeutet genau? O(logn).
Ran G.
Ein kleiner Hinweis: In den klassischen Turing Machine-Einstellungen sind alle Algorithmen , da sie jedes Symbol der Eingabe mindestens einmal lesen müssen. Die binäre Suche kann in O ( log n ) erfolgen, da wir versprechen, dass die Liste beispielsweise sortiert ist. Ω(n)O(logn)
Chazisop
1
Ein später Beitrag: Definitionsgemäß ist der Logarithmus zur Basis einer Zahl n genau die Häufigkeit, mit der Sie b mit sich selbst multiplizieren , um n zu erhalten . b l = nbnbn . Zum Beispiel 2 3 = 8bl=nl=logb(n) . Also, wenn Sie eine Zahl n haben und herausfinden möchten, was l o g b ( n ) = ? dividiere es einfach durch b, bis du eine 1 erreichst (angenommen, n ist derEinfachheit halbereine Potenz von b ). Die Anzahl der Unterteilungen ist gleich l o g b ( n ) . Algorithmen, die dieses Unterteilungsverhalten aufweisen, haben Laufzeiten in O ( l o g23=8log2(8)=3nlogb(n)=?b1nblogb(n) . O(log(n))
Saadtaame

Antworten:

53

Die -Komplexität ist normalerweise mit der Unterteilung verbunden. Stellen Sie sich am Beispiel von Listen eine Liste vor, deren Elemente sortiert sind. Sie können in dieser Liste in O ( log n ) -Zeit suchen. Aufgrund der Sortierung der Liste müssen Sie nicht jedes Element einzeln betrachten.Θ(logn)O(logn)

Wenn Sie sich das Element in der Mitte der Liste ansehen und es mit dem gesuchten Element vergleichen, können Sie sofort feststellen, ob es in der linken oder rechten Hälfte des Arrays liegt. Dann können Sie einfach diese eine Hälfte nehmen und den Vorgang wiederholen, bis Sie sie finden oder eine Liste mit 1 Element erreichen, die Sie trivial vergleichen.

Sie können sehen, dass die Liste jeden Schritt effektiv halbiert. Wenn Sie also eine Liste mit der Länge , müssen Sie maximal 5 Schritte ausführen, um eine Liste mit einem Element zu erreichen . Wenn Sie eine Liste von 128 = 2 7 Elementen haben, benötigen Sie nur 7 Schritte, für eine Liste von 1024 = 2 10 benötigen Sie nur 10 Schritte usw.325128=2771024=21010

Wie Sie sehen, gibt der Exponent in 2 n immer die Anzahl der erforderlichen Schritte an. Der Logarithmus wird verwendet, um genau diese Exponentenzahl zu "extrahieren", zum Beispiel log 2 2 10 = 10 . Es wird auch verallgemeinert, um Längen aufzulisten, die keine Zweierpotenzen sind.n2nlog2210=10

Karel Petranek
quelle
4
Es ist zu beachten, dass dies nur O(log n)dann der Fall ist, wenn die Liste zeitlich konstanten Direktzugriff hat. Bei typischen Listenimplementierungen (verknüpfte Listen) ist diesO(n log n)
asm
1
Die binäre Suche funktioniert nicht bei Listen, da keine Zeiger vorhanden sind. Es wird normalerweise auf Arrays ausgeführt.
Raphael
Bei Listen funktioniert die binäre Suche einwandfrei. Es ist einfach ziemlich sinnlos, da es viel komplizierter als nötig / nützlich / praktisch ist.
Anton
@ AndrewMyers Suche in einer verknüpften Liste ist genauer O(n)
phant0m
1
@ phant0m Ja, ich habe ein bisschen Zeit gebraucht, um herauszufinden, dass ich davon ausgehe, dass Sie sich von der aktuellen Position bewegen, anstatt jedes Mal von Anfang an zu überqueren.
asm
38

In Bezug auf (ausgeglichene) Bäume (z. B. Binärbaum, alle sind also Basis 2):log

  • bekommt die Wurzel des BaumesΘ(1)
  • ist ein Weg von der Wurzel zum BlattΘ(logn)
  • Θ(n)
  • Θ(n2)
  • Θ(nk)kk
  • Θ(2n)k=1,2,,n
Ran G.
quelle
5
Θ(loglogn)T(n)=T((n))+1log(n)
17

O(logn)n

Beispielsweise können Sie bei der binären Suche die Problemgröße bei jeder Vergleichsoperation um die Hälfte reduzieren.

O(logn)O(logn)O(logn)logn

Ken Li
quelle
1
Was wäre es, wenn der Absenkungsbetrag nicht konstant wäre?
Svish
O(logn)
Ja, ich wollte damit sagen, dass der Platz für die Problemrecherche immer kleiner wurde, aber nicht unbedingt mit einer konstanten Rate. Denken Sie nur an Ihren "Solange der Prozentsatz und die zum Verringern der Problemgröße verwendete Operation konstant bleiben, handelt es sich um einen O (log n) -Algorithmus". Wenn es einen anderen Namen hätte, wenn der Prozentsatz dort nicht konstant wäre.
Svish
8

Denken Sie an einen Algorithmus, um die Dezimalzahl umzuwandelnn

while n != 0:
   print n%2, 
   n = n/2

whilelog(n)

Pratik Deoghare
quelle
1
lognO(f(s))ss=lognO(s)
@jmad Richtig. Aber dieses Beispiel gibt Ihnen einen Einblick in log (n).
Pratik Deoghare
@jmad Ich hätte den Algorithmus auch verwenden können, um Zufallszahlen zu generieren, aber ich wollte, dass es so einfach wie möglich ist.
Pratik Deoghare
8

log(n)1n1nlog(n)

100210021002100100210021002100

10021001002100210021001002100log(n)n

Woher kommen Exponentation und Logarithmen? Warum interessieren sie sich so sehr für Informatik? Sie werden es vielleicht nicht bemerken, aber Exponentation ist überall. Haben Sie die Kreditkarte verzinst? Sie haben gerade ein Universum für Ihr Zuhause bezahlt (nicht so schlecht, aber die Kurve passt). Ich denke gerne, dass die Exponentation von der Produktregel herrührt, aber andere können gerne weitere Beispiele nennen. Was ist die Produktregel, können Sie fragen; Und ich werde antworten.

ABCBCACDCAD2342421010242101010210101024

log2(n)nn2n2logb(n)bbnlog(n)nn

log(n)n

Ravi
quelle
3
log(n)
3
Ich habe versucht, eine Vorstellung davon zu geben, wie klein es ist.
Ravi
5

O(logn)x

Es basiert immer noch auf der Größe der Liste, aber Sie müssen nur einen Bruchteil der Elemente besuchen.

dpatchery
quelle
4

Θ(lgkn)Θ(lgk+1n)

Θ(1)lgn

Der binäre Suchalgorithmus ist das klassische Beispiel.

Kaveh
quelle
1

Die Intuition ist, wie oft Sie eine Zahl, sagen wir n, halbieren können, bevor sie auf 1 reduziert wird, ist O (lg n).

Zeichnen Sie es zur Visualisierung als Binärbaum und zählen Sie die Anzahl der Ebenen, indem Sie diesen geometrischen Verlauf lösen.

2^0+2^1+...+2^h = n
user1234
quelle
lognn