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

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 .$\Theta(n)$$\Theta(n\log n)$$\Theta(n/\log n)$$\Theta(n \log n)$$\Theta(n/\log n)$$\Theta(n^f)$$0 < f < 1$

Wie entscheiden wir uns beispielsweise für vs. oder$\Theta(n/\log n)$$\Theta(n^{2/3})$$\Theta(n^{1/3})$

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

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:

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.

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.$\log n$$2^n$$2^n$$n^k$$k$$\log n$$n^k$$k$

gegen n k , für k < 1 ist identisch mit: n / log n gegen n / n 1 - $n / \log n$$n^k$$k < 1$$n / \log n$$n / n^{1-k}$

als für großes n , n / log n > n k für k < 1 und großes n .$n^{1-k} > \log n$$n$$n / \log n > n^k$$k < 1$$n$

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

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).

$n^f$$\dfrac{n}{n^{1-f}}$$n^{2/3}=n/n^{1/3}$

$\log n$$n^\varepsilon$$\varepsilon>0$

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

$f \prec g$

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

Angewandt auf Ihr Beispiel:

$\mathcal{O}(n/\log n) \Rightarrow (1, -1, 0)$

$\mathcal{O}(n^{2/3}) \Rightarrow (2/3, 0, 0)$

$\mathcal{O}(n^{1/3}) \Rightarrow (1/3, 0, 0)$

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

Quelle: Konkrete Mathematik, S. 441