# Komplexitätsklasse



## hos15 (25. Jan 2017)

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 (26. Jan 2017)

keiner eine Idee ? echt jetzt ?


----------



## CSHW89 (26. Jan 2017)

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 (26. Jan 2017)

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 (26. Jan 2017)

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 (26. Jan 2017)

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 (26. Jan 2017)

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 (26. Jan 2017)

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 (26. Jan 2017)

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 (26. Jan 2017)

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 (26. Jan 2017)

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


----------



## CSHW89 (26. Jan 2017)

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 (26. Jan 2017)

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 (26. Jan 2017)

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 (26. Jan 2017)

Ok vielen dank das werde ich aufjedenfall mitnehmen


----------

