| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
habeinefrage
Gast
|
 Verfasst am: 27. Dez 2005 15:20 Titel: Komplexität bestimmen |
 |
|
hi,
wie kann ich die Komplexität eines rekursiven Aufrufs der Form
T(n)=2*T(n/4)+2*b*n
bestimmen? |
|
| Nach oben |
|
 |
|
|
Senior Sanchez
Gast
|
| Verfasst am: 27. Dez 2005 20:14 Titel: |
|
|
Na am einfachsten ist es, wenn du dir für die variable Größe (ich denke mal n?) verschiedene Werte einsetzt und schaust wieviel Rekursionsschritte jedesmal entstehen.
Also beginnst mit n=1, dann n = 2 usw. und je nachdem wie stark dann der Rechenaufwand steigt, sprich je mehr Iterationensschritte/Rekursionsschritte ausgeführt werden müssen umso höher ist die Komplexität. |
|
| Nach oben |
|
|
Tobias
Anmeldungsdatum: 15.02.2005
Beiträge: 149
|
| Verfasst am: 28. Dez 2005 14:09 Titel: |
|
|
Ich glaube das lässt sich auch ein wenig mathematischer angehen.
Die Stichworte bei Rekursionen sind zum einen "sukkzessives Einsetzen" und zum anderen "Mastertheorem".
In deinem Fall kommst du mit dem Mastertheorem gut weiter. Infos dazu findest du hier: http://www.grundstudium.info/algorithmen/node3.php |
|
| Nach oben |
|
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
