0 Daumen
2,5k Aufrufe



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
    log2 log2 (n)
    log2 (n)
   \( \sqrt[3]{n} \)
   \( \sqrt{n} \)
    n
    n * log (n)
    n ²
    n² * log3 (n²)
    n² * log3 (n³)
    n² * log2 (n²)
    n³ * log2 (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)  =  (log3n)2

f5(n)  =  log2(n3)

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?

Avatar von

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 log3(n)² und f5 (n) ist log2(n³).

log3(n)² wäre ja log3(n) * log3 (n).

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

Wenn man es bei desmos.calculator eingibt, steht jedoch, dass log3(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

log3 (n) = log (n) / log (3)

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

Dementsprechend müsste log3(n)², also log3 (n) * log3 (n) der Logik nach doch auch langsamer wachsen als log2(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!

2 Antworten

+1 Daumen

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

Avatar von 86 k 🚀
+1 Daumen

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:

Bildschirmfoto von 2019-08-20 00-14-27.png

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.

Avatar von 14 k

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² * log3 (n²)

n² * log3 (n³)

n² * log2 (n²)

n² * log3 (n²)

n³ * log2 (n³)

n³ * log3 (n²)

n³ * log3 (n³)

n³ * log2 (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² * log2 (n²)

n² * log2 (n³)

n² * log3 (n²)

n² * log3 (n²)

n³ * log2 (n³)

n³ * log2 (n²)

n³ * log3 (n³)

n³ * log3 (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: log3(x) wächst langsamer als log2(x).

Nachtrag:

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

Bildschirmfoto von 2019-08-20 02-17-17.png

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community