Komplexitätsklasse

[hos15]

Hallo alle zusammen in welcher Komplexitätsklasse liegen die folgenden Aufwände:

1) T(n) =3n^{3} + n^{2} + 100
2) T(n)=4n^{3} + 2n + log( n)
3) T(n)=n^{3} +3e^{n}

bei der 1 bin ich mir ziemlich sicher und zwar liegt
1) In der Komplexitätsklasse O(n^3) da der Grenzwert T(n)/n^3 exisitiert und gleich 3 ist.
2) und 3) weiß ich leider nicht..

 

[hos15]

keiner eine Idee ? echt jetzt ?

 

[CSHW89]

Wie lautet die Frage denn genau? Komplexitätsklassen haben mit der O-Notation nur bedingt zu tun. Siehe auch: https://de.wikipedia.org/wiki/Komplexitätsklasse
Somit wäre die Lösung zu 1 z.b. "P", da polynomiell beschränkt.

Oder soll man eine möglichst gute Abschätzung der Funktion T in O-Notation finden? Dabei sucht man sich bei der Addition von Funktionen, diejeniger raus, die am schnellsten wächst, und prüft, ob die Definition von O erfüllt ist:
https://de.wikipedia.org/wiki/Landau-Symbole#Definition
Ich denke mal, ihr hattet in der Vorlesung die dritte Tabelle als Definition.

lg Kevin

 

[hos15]

Die genaue Frage lautet:

In welcher Komplexitätsklasse liegen Algorithmen mit folgenden Aufwänden:
(a) 3n^3 + n^2 + 100
(b) 4n^3 + 2n + log n
(c) n^3 + 3e^n

Ich habe dazu einfach bsp.weise bei a) T(n) = 3n^3 + n^2 + 100 und G(n) = n^3 und wenn der Grenzwert
gegen unendlich T(n) / G(n) exisitiert dann muss T(n) in G(n) liegen. Da der Grenzwert existiert mit lim T(n) / G(n) =3 muss T(n) in O(G(n)) liegen. So habe ich es in jeder Aufgabe gemacht ist das ok ?

 

[CSHW89]

Eigentlich kenne ich den Termius Komplexitätsklasse in einem anderen Zusammenhang (siehe wiki-Link). Aber wenn es in der Aufgabe wirklich um die O-Notation geht, dann ja. Das wäre dann die erste Tablle hier:
https://de.wikipedia.org/wiki/Landau-Symbole#Definition

Wo hakt es denn bei den anderen Aufgaben? Welcher Term würdest du denn sagen, dominiert bei (b) und bei (c)?

 

[hos15]

Wie kennst du den ? Wie würdest du Bsp.weise die a) lösen ?
bei b) und c) wäre es wieder O(n^3) deswegen finde ich das so Komisch. Alle Aufwände würden dann in der Komplexitätsklasse O(n^3) hmm 🙁

 

[CSHW89]

Wie schon in meinem ersten Post wäre meine Lösung von (a) "P", da polynomiell beschränkt.
(b) ist in O(n^3), (c) jedoch nicht. Die e-Funktion wächst immer schneller, als jedes n^x mit beliebigen x. Wie würdest du denn den Limes in (b) berechnen? Schon mal von "Regel von de l'Hospital" gehört?

 

[hos15]

Ja klar ich bin Mathestudent 😀
aber wenn ich in c) den Grenzwert ausrechne für n^3 dann Kriege ich ein Grenzwert raus Mhh..
übrigens ich rechne mit einem Grenzwertrechner...

 

[CSHW89]

Tut mir leid, dann ist dein Grenzwertrechner mist:
http://www.wolframalpha.com/input/?i=limit((n^3+3*e^n)/n^3,+n=infinity)

 

[hos15]

ja das habe ich gemerkt ...
Aber wenn ich so eine Aufgabe habe wie soll ich G(n) bestimmen ? Bei den Funktionen von eben war es ja noch leicht aber hier fällt mir es etwas schwer. Oder nein Wenn e^n sehr schnell wächst dann muss ich im nenner eine Funktion finden die genau so schnell wächst und das ist ja gerade e^n selbst und wenn ich den Grenzwert davon ausrechnen würde so müsste 3 rauskommen. Bsweise so :

n^3/e^n + 3* e^n/e^n

da e^n schneller wächst als n^3 geht das gegen unendlich gegen 0 also bleibt 3 übrig

 

[hos15]

also muss T(n) in O(e^n) liegen.. oder ?

 

[CSHW89]

Ja die Begründung ist ein wenig schwammig. n^3/e^n kann man mit dreifachem l'Hospital vereinfachen zu 6/e^n, was mit n->infinity 0 ist. Also ist der Grenzwert 3 und T(n) liegt in O(e^n).

 

[hos15]

Ok ich verstehe danke 🙂 und könntest du mir ein tipp geben wie ich das erkennen kann welche Komplexitätsklasse vorliegt ? Ich würde ungern in der Klausur ein fehler machen wie bei der c)

 

[CSHW89]

Bei Addition immer den dominaten Term nehmen, also, der der schneller wächst. Bei Multiplikation die einzelnen Terme separat betrachten, und die dominanten Terme wieder multiplizieren:
Z.b.: (e^n+n^3)*(log(n)+log(log(n))) € O(e^n * log(n))

 

[hos15]

Ok vielen dank das werde ich aufjedenfall mitnehmen 🙂