n * log n und n / log n gegen die Polynomlaufzeit

12

Ich verstehe, dass schneller als Θ ( n log n ) und langsamer als Θ ( n / log n ) ist . Was schwierig ist , ist für mich zu verstehen , wie eigentlich vergleichen Θ ( n log n ) und Θ ( n / log n ) mit Θ ( n f ) wobei .Θ(n)Θ(nlogn)Θ(n/logn)Θ(nlogn)Θ(n/logn)Θ(nf)0<f<1

Wie entscheiden wir uns beispielsweise für vs. oderΘ(n/logn)Θ(n2/3)Θ(n1/3)

Ich hätte gerne eine Anleitung, wie ich in solchen Fällen vorgehen soll. Vielen Dank.

mihsathe
quelle

Antworten:

3

Wenn Sie nur ein paar Grafiken zeichnen, sind Sie in guter Verfassung. Wolfram Alpha ist eine großartige Ressource für diese Art von Untersuchungen:

Gleichungen

Graph

Erstellt von diesem Link . Beachten Sie, dass log (x) im Diagramm der natürliche Logarithmus ist, weshalb die Gleichung des einen Diagramms etwas komisch aussieht.


quelle
Abgesehen davon, dass Raphael zustimmt, würde dieses Bild eine viel bessere Vorstellung vermitteln . Wenn Sie einen noch größeren Bereich wählen, verschwindet die zweite Funktion, was verwirrend sein kann.
Phant0m
9

ist die Inverse von 2 n . So wie 2 n schneller wächst als jedes Polynom n k, unabhängig davon, wie groß ein endliches k ist,wächst log n langsamer als alle Polynomfunktionen n k, unabhängig davon, wie klein ein positives k ungleich Nullist.Logn2n2nnkkLognnkk

gegen n k , für k < 1 ist identisch mit: n / log n gegen n / n 1 - kn/Lognnkk<1n/Lognn/n1-k

als für großes n , n / log n > n k für k < 1 und großes n .n1-k>Lognnn/Logn>nkk<1n

Taedrin
quelle
3

Bei vielen Algorithmen kommt es manchmal vor, dass die Konstanten unterschiedlich sind, was dazu führt, dass die eine oder andere Konstante bei kleineren Datengrößen schneller oder langsamer ist und nach algorithmischer Komplexität nicht so geordnet ist.

Davon abgesehen, wenn wir nur die sehr großen Datenmengen berücksichtigen , d.h. was man schließlich gewinnt, ist dann O(n^f)schneller als O(n/log n)für 0 < f < 1.

Ein großer Teil der algorithmischen Komplexität besteht darin, zu bestimmen, welcher Algorithmus letztendlich schneller ist. Daher reicht es oft aus , zu wissen, dass dieser Algorithmus schneller O(n^f)ist als O(n/log n)for 0 < f < 1.

Eine allgemeine Regel ist , daß die Multiplikation (oder dividiert) durch log nschließlich vernachlässigbar sein im Vergleich zu multiplizieren (oder Aufteilen) durch n^ffür jeden f > 0.

Um dies deutlicher zu zeigen, betrachten wir, was passiert, wenn n zunimmt.

   n       n / log n         n^(1/2)
   2        n/ 1              ?
   4        n/ 2             n/ 2
   8        n/ 3              ?
  16        n/ 4             n/ 4
  64        n/ 6             n/ 8
 256        n/ 8             n/16
1024        n/10             n/32

Beachten Sie, was schneller abnimmt? Es ist die n^fSäule.

Selbst wenn fnäher an 1 liegt, n^fstartet die Spalte nur langsamer, aber wenn sich n verdoppelt, beschleunigt sich die Änderungsrate des Nenners, während sich der Nenner der n/log nSpalte mit einer konstanten Rate zu ändern scheint.

Lassen Sie uns einen bestimmten Fall in einem Diagramm darstellen

Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

Quelle: Wolfram Alpha

Ich habe so gewählt O(n^k), dass kes ziemlich nahe an 1 (at 0.9) liegt. Ich habe auch die Konstanten so gewählt, dass sie anfangs O(n^k)langsamer sind. Beachten Sie jedoch, dass es letztendlich "gewinnt" und weniger Zeit in Anspruch nimmt als O(n/log n).

ronalchn
quelle
was ist mit n / log n
Das war ein bisschen ein Tippfehler, das habe ich am Anfang gemeint. Wie auch immer, ich habe ein passenderes Diagramm hinzugefügt, das zeigt, dass es n^kmöglicherweise schneller ist, auch wenn Konstanten so ausgewählt sind, dass sie anfänglich langsamer sind.
3

nfnn1-fn2/3=n/n1/3

nLogngegennn1-f.

Lognnεε>0

A.Schulz
quelle
1

Beim Vergleich von Laufzeiten ist es immer hilfreich, sie mit großen Werten von n zu vergleichen. Für mich hilft dies dabei, die Intuition darüber aufzubauen, welche Funktion langsamer ist

Denken Sie in Ihrem Fall an n = 10 ^ 10 und a = .5

O(n/logn) = O(10^10/10) = O(10^9)
O(n^1/2) = O(10^10^.5) = O(10^5)

Daher ist O (n ^ a) schneller als O (n / logn). Wenn 0 <a <1 ist, habe ich nur einen Wert verwendet. Sie können jedoch mehrere Werte verwenden, um eine Intuition über die Funktion zu erhalten


quelle
1
Schreiben Sie nicht O(10^9), aber der Hauptpunkt beim Versuch, mit Zahlen eine Intuition aufzubauen, ist richtig.
Scheitern. Das ist nicht richtig. Sie haben eine einzelne n-Konstante eingesetzt, die möglicherweise voreingenommen ist. Wenn ich verschiedene Konstanten wählen würde, könnte jeder Algorithmus besser aussehen. Die Big-O-Notation wird verwendet, um Trends zu ermitteln, die langfristig schneller sind. Dazu muss man zeigen können, dass es für großes n schneller ist, auch wenn es langsamer ist, wenn n kleiner ist.
Vielen Dank. Hinzugefügt mehrere Werte Teil und größere Zahlen zu berücksichtigen
Es sollte beachtet werden, dass nur, weil f (a)> g (a) für eine Konstante a ist, nicht notwendigerweise impliziert, dass O (f (x))> O (g (x)) ist. Dies ist nützlich, um Intuition aufzubauen, reicht jedoch nicht aus, um einen strengen Beweis zu erstellen. Um zu zeigen, dass diese Beziehung gilt, müssen Sie zeigen, dass dies für ALLES große n gilt, nicht nur für ein großes n. Ebenso müssen Sie nachweisen, dass es für alle Polynome positiven Grades <1 gilt.
1

fG

nα1(Logn)α2(LogLogn)α3nβ1(Logn)β2(LogLogn)β3(α1,α2,α3)<(β1,β2,β3)

(2,10)<(3,5)(2,10)>(2,5)

Angewandt auf Ihr Beispiel:

Ö(n/Logn)(1,-1,0)

Ö(n2/3)(2/3,0,0)

Ö(n1/3)(1/3,0,0)

(1/3,0,0)<(2/3,0,0)<(1,-1,0)Ö(n1/3)Ö(n2/3)Ö(n/Logn)

Man könnte sagen: Potenzen von n dominieren die Potenzen von log, die die Potenzen von log log dominieren.

Quelle: Konkrete Mathematik, S. 441

phant0m
quelle