Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Komplexitätstheorie
Gehe zu Seite 1, 2  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Komplexitätstheorie
 
Autor Nachricht
Exavier
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 04.10.2006
Beiträge: 161
Wohnort: Jena

BeitragVerfasst am: 05 Nov 2006 - 15:49:01    Titel: Komplexitätstheorie

Hallo liebes Forum,
stehe hier vor einem kleinen Problem. Mir fehlt da eine Idee. Die Aufgabe stammt aus einer Übungsserie bei uns in der Uni.

Geben Sie asymptotische obere Schranken für T(n) in den folgenden
Rekurrenzen an. Begründen Sie Ihre Lösungsvorschläge.

T(n) = 5T(n/5) + n^2

Begründen ist denke ich schlicht die Rechnung. Da is bei mir nur nen wie... ich hab dann gleich mal Wikipedia gefragt und das sagte mir dann:

f€O(g) asymptodischeobere Schranke 0<= limsup(x->a) |f(x)/g(x)| <+infi.

das bringt mich allerdings nicht weiter.

jemand von euch eine idee?

mfg

exa
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24257

BeitragVerfasst am: 05 Nov 2006 - 15:51:14    Titel:

Hallo!

Hattet ihr das Master-Theorem schon? wenn ja, dann einfach einsetzen, und fertig. Smile


Wenn nein, dann kannst du ja einfach mal die sich ergebende Reihe berechnen... Smile


Viele Grüße, Cyrix
Exavier
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 04.10.2006
Beiträge: 161
Wohnort: Jena

BeitragVerfasst am: 05 Nov 2006 - 15:54:34    Titel:

doch hatten wir wen ich nicht irre... ich wühl mal in den aufzeichnungen Very Happy
Exavier
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 04.10.2006
Beiträge: 161
Wohnort: Jena

BeitragVerfasst am: 05 Nov 2006 - 16:13:54    Titel:

also master-theorem sagt ja

T(n) = a*T(n/b)+f(n)

dann hab ich ja a=5, b=2 f(n) = n^2
dann muss wohl ( denke ich ) f(n) € (n^(log_b a - epsilon)

für epsilon 1 stimmt das da ln5/ln2 ja 2,xxx ist

aber jetzt komm ich net weiter irgendwie
Exavier
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 04.10.2006
Beiträge: 161
Wohnort: Jena

BeitragVerfasst am: 05 Nov 2006 - 16:27:08    Titel:

ps: oder reicht das schon wenn ich sage, da mein oben getipptes ja offenbar stimmt, wächst ist T(n) € O(n^2) ?
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24257

BeitragVerfasst am: 05 Nov 2006 - 16:28:51    Titel:

Dein b ist nicht 2, sondern 5... Wink

Viele Grüße, Cyrix
Exavier
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 04.10.2006
Beiträge: 161
Wohnort: Jena

BeitragVerfasst am: 05 Nov 2006 - 16:34:00    Titel:

ups..

naja dann n^2 € O(n^(1-epsilon))

da aber epsilon > 0 sein muss finde ich doch keins, mit dem O dann schneller wächst als n^2.. nu bin ich verwirrt
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24257

BeitragVerfasst am: 05 Nov 2006 - 16:37:04    Titel:

Hallo!

Dein n^2 liegt nicht in O(n^(1-epsilon)), es liegt sogar in Omega(n^(1+epsilon)) für jedes epsilon<1... Wink

Schau dir das Master-Theorem nochmal genau an. Das hat Aussagen über 3 verschiedene Fälle gemacht. Der obige ist einer davon... Smile


Viele Grüße, Cyrix
Exavier
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 04.10.2006
Beiträge: 161
Wohnort: Jena

BeitragVerfasst am: 05 Nov 2006 - 17:10:00    Titel:

also ich habe

T(n) = 5T(n/5) + n^2

a = b = 5, f(n) = n^2

n^2 € Omega(n^(1+epsilon)) ... wähle epsilon = 1 folgt

n^2 € omega(n^2)

dann nächste bedingung ist

a*f(n/b) <= c*f(n)
einsetzen gibt

5*(n/5)^2 == 1/5*n^2 <= c*n^2.. wähle c = 1/5

somit is T(n) = O(n^2) = O(mit strich durchs O)(n^2) = Omega(n^2)


stimmt das?
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24257

BeitragVerfasst am: 05 Nov 2006 - 17:13:08    Titel:

Richtig! Smile

Ja, das O mit dem Strich durch ist übrigens ein Theta Wink (wie heißen T(n) ist in O(n^2) und gleichzeitig in Omega(n^2). Smile )

Viele Grüße, Cyrix
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Komplexitätstheorie
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite 1, 2  Weiter
Seite 1 von 2

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum