3.x Video: complexity

Tobi, der laute
Erstie
Erstie
Beiträge: 15
Registriert: 14. Mai 2015 00:28

3.x Video: complexity

Beitrag von Tobi, der laute »

Ich habe eine Frage bezüglich des Komplexitätsvideo von Karsten
(link: https://openlearnware.hrz.tu-darmstadt. ... exity-2175 )

Bei timestamp 15:30 sagt Karsten, dass die Funktion f asymptotisch schneller wächst als die Funktion g, wenn lim (f/g) = 0 gilt.

Bei timestamp 21:40 sagt er allerdings, dass der natürliche logarithmus (ln x) schneller wächst als die Konstante Funktion (1), da:

lim 1 / ln x = lim (0/x^-1) = 0 gilt, nach L'Hôpital.

In diesem Fall wäre f = 1 und g = ln x und damit würde doch der natürliche Logarithmus langsamer wachsen, als c, oder?

Hier liegt irgendwo ein Widerspruch vor. Die Frage ist nur, ob Karsten nur falsch Argumentiert, oder seine Aussage falsch ist.

~Tobi

PS: Bei de zweiten Beispiel scheint der gleiche Widerspruch aufzutreten

Benutzeravatar
felicis
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 114
Registriert: 14. Apr 2015 20:25

Re: 3.x Video: complexity

Beitrag von felicis »

\[ \lim_{n \to \infty} {f(n) \over g(n)} = 0 \quad \implies \quad \text{"g wächst asymptotisch schneller als f"} \]

Du hast recht, da muss ein Fehler sein (wenn es so ist, wie du sagst)

felicis

Tobi, der laute
Erstie
Erstie
Beiträge: 15
Registriert: 14. Mai 2015 00:28

Re: 3.x Video: complexity

Beitrag von Tobi, der laute »

Ja! So wie du es aufgeschrieben hast ergibt das sogar Sinn!

Also ist die Grundprämisse des zweiten Teils des Videos falsch, aufgrund eines simplen Versprechers.

Nichts desto trotz, gilt dennoch Karstens Aussage über den natürlichen Logarithmus, wenn man die korregierte "natürliche Definition" annimmt.

Ich danke dir, jetzt wird mir einiges klarer.

Janosch
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 17. Mär 2014 14:28

Re: 3.x Video: complexity

Beitrag von Janosch »

Ich gehe mal von aus das er mit "schneller" die Laufzeit gemeint hat.

Ich teste solche Ungereimtheiten anhand einfacher Eigenbeispiele:


Für \(f(x) = x^2\) und \(g(x) = x^3\) gilt:

\[\lim_{x \to \infty}{x^2 \over x^3} \quad \implies \quad \lim_{x \to \infty}{2x \over 3x^2} \quad \implies \quad \lim_{x \to \infty}{2 \over 6x} = 0\]
\[demnach\]
\[\lim_{x \to \infty}{f(x) \over g(x)} = 0\]

Somit wächst \(g(x)\) asymtotisch schneller und \(f(x) \in O(g)\) da \(f(x)\) nicht so komplex ist bzw. die Komplexität eines schnelleren Algorithmus beschreibt als \(g(x)\).

Tobi, der laute
Erstie
Erstie
Beiträge: 15
Registriert: 14. Mai 2015 00:28

Re: 3.x Video: complexity

Beitrag von Tobi, der laute »

Ahhh, also ist

"f ist asymptotisch schneller als g" <=> "f wächst langsamer als g"
bzw.
"f ist asymptotisch langsamer als g" <=> "f wächst schneller als g"

Oha, gefährliche Wortwahl...

d110
Erstie
Erstie
Beiträge: 13
Registriert: 13. Apr 2015 19:28

Re: 3.x Video: complexity

Beitrag von d110 »

Ein Problem ist glaube ich, dass folgendes aus dem Video falsch ist:

" lim 1 / ln x = lim (0/x^-1) = 0 gilt, nach L'Hôpital. "

Man darf die Regel von d. l. H. nur auf uneigentliche Grenzwerte also -> unendlich/unendlich oder 0/0 anwenden.

Antworten

Zurück zu „Archiv“