Wachstumshierarchie bei Logarithmen

Question

für eine Klausur in Algorithmentheorie und Datenstrukturen, sollen wir vorgegebene Funktionen ihren asymptotischen Wachstum ordnen. Ich bin mir allerdings unsicher, wie genau die Wachstumshierarchie von Funktionen aussieht. Habe mal versucht, selbst eine zu erstellen, und bin nicht sicher, ob sie korrekt ist

(von langsam nach schnell sortiert)

    1
    log₂ log₂ (n)
    log₂ (n)
   \( \sqrt[3]{n} \)
   \( \sqrt{n} \)
    n
    n * log (n)
    n ²
    n² * log₃ (n²)
    n² * log₃ (n³)
    n² * log₂ (n²)
    n³ * log₂ (n³)
    n³ * log
    2^n

Ist das so richtig? Insbesondere bei den letzten 6 Punkten, bin ich mir extrem unsicher. Kennt jemand einen Link, wo eine offizielle Wachstumshierarchie aufgeführt wird? Wie gehe ich bei so was am besten vor. z.B. bei der folgenden Aufgabe

"""Es seien die folgenden Funktionen von N>0 nach R gegeben:

f1(n)  =\( \frac{2n}{3} \)

f2(n)  =  3^{(log_3 27)·n/3}

f3(n)  =  2^{(log_2 4)·n/2}

f4(n)  =  (log₃n)²

f5(n)  =  log₂(n³)

f6(n)  = \( \sqrt[3]{n²} \)

Ordnen Sie die Funktionen nach ihrem asymptotischen Wachstum beginnend mit der am langsamsten wachsenden Funktion""

Ich hätte jetzt, basierend auf meiner selbst erstellten Wachstumshierarchie gesagt

f4 (weil log ²) < f5 (weil ³ ist mehr als ²), < f6 < f1 (wegen n) < f3 < f2.

Richtig oder bin ich total auf dem falschen Dampfer?

Comments

Das ist keine schöne Aufgabe (meiner Meinung nach). Zur Kontrolle kannst du die Funktionen plotten:

https://www.desmos.com/calculator

---

Danke für den Link. Sehr hilfreich :)

---

Kannst du mir vielleicht bitte noch sagen, wieso f5 (n) langsamer wächst als f4 (n)

f4(n) ist log₃(n)² und f₅ (n) ist log2(n³).

log₃(n)² wäre ja log₃(n) * log₃ (n).

Und ich hätte jetzt gedacht log₃ wächst doch viel langsamer als log₂(n³), weil log₃ langsamer wächst als log₂.

Wenn man es bei desmos.calculator eingibt, steht jedoch, dass log₃(n)² schneller wächst.

---

Wenn man es bei desmos.calculator eingibt, steht jedoch, dass log3(n)² schneller wächst.

Für genügend große \(n\). Hier \(n>185.634\) sieht man graphisch, dass \(f_5(n)\) langsamer wächst als \(f_4(n)\).

Du könntest auch beweisen, dass für \(x>0\) und \(b>1\) gilt:$$\log_{b}{x}=\log(x)/\log(b)$$ und dann zeigen, dass \(f_5(n) \ll f_4(n)\).

---

Danke. Ja, ich sehe es im Desmod-Calculator und auch wenn man hinreichend große Werte im Taschenrechenr eingibt. In der Klausur haben wir jedoch keinen TR zur Verfügung. :(

Wie meinst du das mit dem Beweis? also zeigen dass

log₃ (n) = log (n) / log (3)

In der Vorlesung haben wir halt gelernt dass log₂ log₂ (n) langsamer wächst als log₂ (n)

Dementsprechend müsste log₃(n)², also log₃ (n) * log₃ (n) der Logik nach doch auch langsamer wachsen als log₂(n³)?

Tut mir leid, ich kann durch die Graphik nachvollziehen, dass f5 (n) kleiner ist als f4 (n), aber ich verstehe nicht, wie man das formell zeigen kann. :(

---

Ich setze für \(x>0\) und \(b>1\) folgenden Zusammenhang als Voraussetzung voraus: \(\log_{b}{x}=\frac{\log x}{\log b}\).

Dann schreibst du:$$(\log_{3}{n})^2=\left(\frac{\log n}{\log3}\right)^2=\frac{1}{(\log 3)^2}\cdot (\log n)^2$$$$\log_{2}{n^3}=\frac{\log n^3}{\log 2}=\frac{3}{\log 2} \cdot \log n$$ Um nun nachzuweisen, dass \(f_5(n) \ll f_4(n)\), betrachte:$$\lim\limits_{n\to\infty}\frac{f_5(n)}{f_4(n)}\overset{!}{=}0$$ Also:$$\lim\limits_{n\to\infty}\frac{\frac{3}{\log 2}\cdot \log n}{\frac{1}{(\log 3)^2}\cdot (\log n)^2}=\lim\limits_{n\to\infty}\frac{\frac{3}{\log 2}}{\frac{1}{(\log 3)^2}\cdot \log n}=0$$ Oben im Zähler hast du nur eine Konstante und es sollte bekannt sein, dass \(\log\) als Umkehrfunktion von \(e^x\) streng monoton wächst!

Answer 1

Hallo Marceline,

https://www7.in.tum.de/um/courses/ds/ws0910/folien_generated/07-Grundlagen-Wachstum.pdf

(Seite 35)

Danach gilt   \( f < g  ⇔  \lim\limits_{n\to\infty}\dfrac{|f(n)|}{g(n)}=0\)

zum Beispiel:

 \( \dfrac{log_2(log_2(n))}{log_2(n)} = \dfrac{log_2(u)}{u}→_{u→∞}0\)

 \(\dfrac{ n^2·log_{2}(n^2) } { n^3·log_2(n^3)}= \dfrac{2·log_2(n)}{n·3·log_2(n)}=\dfrac{2}{3n}→_{n→∞}0 \)

Nachtrag:

Aber:

\( \dfrac{n^2·log_3(n^3)}{n^2·log_2(n^2)}= \dfrac{\frac{ln(n^3)}{ln(3)}}{\frac{ln(n^2)}{ln(2)}} =\dfrac{3·ln(2)}{2·ln(3)}\)

 Gruß Wolfgang

Answer 2

Du kannst dir ja mal eine Art Ranking erstellen, indem du den Grenzwert von

$$ \lim_{x \to \infty} \frac{f_i(x)}{f_j(x)} $$

untersuchst. Damit erstellst du dir eine Tabelle. Beispielhaft sowas:

Ich betrachte es hier zeilenweise. Die i-te Zeilen mit den meisten 0 als Grenzwert ist die langsamste Funktion. Die einzelnen Grenzwerte kannst du ja bei Wolfram-Alpha berechnen lassen.

Ist zwar ein Aufwand von θ(n^2), aber so kann man vorgehen, wenn man keine Ahnung mehr hat.

EDIT: Falls man aber mehrere Funktionen gleicher Klasse haben sollte, sind auch ihre konstanten Faktoren wichtig, zu beachten.

Comments

Danke für die Antwort, hallo97.

D.h. mir bleibt nichts anderes übrig, als jedes mal die Regel von L'Hopital anzuwenden und den Grenzwert zu betrachten?

Meine Frage wäre, wenn man z.B. so Funktionen (von mir erfunden) hat wie:

n² * log₃ (n²)

n² * log₃ (n³)

n² * log₂ (n²)

n² * log₃ (n²)

n³ * log₂ (n³)

n³ * log₃ (n²)

n³ * log₃ (n³)

n³ * log₂ (n²)

Würde man doch zuerst den Faktor n² bzw. n³ betrachten und alles was n² hat, würde schon mal asymptotisch langsamer wachsen, als alles was n³ vorne als Faktor stehen hat? Als nächstes dann die Logarithmen betrachten, also alles was log2 ist, wächst langsamer als log3 und zum Schluss, dass was innerhalb der Logarithmus-Klammer steht. Dann wäre die Ordnung am Ende

n² * log₂ (n²)

n² * log₂ (n³)

n² * log₃ (n²)

n² * log₃ (n²)

n³ * log₂ (n³)

n³ * log₂ (n²)

n³ * log₃ (n³)

n³ * log₃ (n³)

Kann man allgemein nach diesem Schema eine Hackordnung aufstellen oder ist das jetzt nur Zufall?

---

Im schlimmsten Fall musst du dann jeden Grenzwert betrachten (L'Hospital), oder man kann schon durch ,,scharfes'' Hinschauen erkennen, wo die Reise hingeht.

Es ist unschön mit Logarithmen unterschiedlicher Basen zu arbeiten. Aber du kannst einen Logarithmusausdruck mithilfe des natürlichen Logarithmuses umschreiben, um so besser sehen zu können, was schneller oder langsamer wächst.

$$ \log_b(x)=\frac{\ln(x)}{\ln(b)} $$

EDIT: log₃(x) wächst langsamer als log₂(x).

---

Nachtrag:

Die einzelnen Vorfaktoren können dann so viel einfacher verglichen werden. Das sieht dann so aus vom Ranking: