Komplexitätsklasse

H

hos15

Aktives Mitglied
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..
 
C

CSHW89

Bekanntes Mitglied
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
 
H

hos15

Aktives Mitglied
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 ?
 
H

hos15

Aktives Mitglied
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 :(
 
C

CSHW89

Bekanntes Mitglied
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?
 
H

hos15

Aktives Mitglied
Ja klar ich bin Mathestudent :D
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...
 
H

hos15

Aktives Mitglied
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
 
C

CSHW89

Bekanntes Mitglied
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).
 
H

hos15

Aktives Mitglied
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)
 
C

CSHW89

Bekanntes Mitglied
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))
 

Aktuelle Jobs

Neue Themen


Oben