Übung 12.2

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Übung 12.2

Beitrag von sab »

Hallo,

ich habe eine Frage zur asymptotischen Komplexitätsklasse des awesomealgos.
Wenn ich das richtig erahne, dann hat der Algorithmus eine polynomielle Laufzeit (verdient er dann noch seinen Namen? :wink:)
Gehe ich nach den Kritzeleien vom 26.04. vor, dann komme ich nicht auf so eine Gleichung, kann also auch nichts wirklich umformen.
Ich sehe zwar eine Entwicklung der Aufrufe, aber die sind nicht polynomiell. Ich habe eine Formel, die besagt (Spoiler, Textfarbe = Standardhintergrundfarbe):
\(3^i \cdot \frac{(2^i) \cdot n}{3^i}\)
Bin ich damit auf dem richtigen Weg oder geht das in die falsche Richtung?

Für einen kleinen Tip besten Dank!

d00p
Neuling
Neuling
Beiträge: 6
Registriert: 4. Jun 2012 18:06

Re: Übung 12.2

Beitrag von d00p »

edit: passt leider doch nicht was ich da hatte

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übung 12.2

Beitrag von Prof. Karsten Weihe »

sab hat geschrieben: ich habe eine Frage zur asymptotischen Komplexitätsklasse des awesomealgos.
Die Beantwortung dieses Postings wurde ediert, so dass Ihre Frage wieder offen ist?

sab hat geschrieben: Ich sehe zwar eine Entwicklung der Aufrufe, aber die sind nicht polynomiell.
Das sind sie bei Mergesort auch nicht. Bei Mergesort wächst die Anzahl der Aufrufe exponentiell in der Rekursionstiefe. Entscheidend ist aber bei Mergesort, dass die Rekursionstiefe logarithmisch beschränkt ist und somit die Gesamtzahl Aufrufe sogar linear in der Länge der Sequenz bleibt.

sab hat geschrieben: Bin ich damit auf dem richtigen Weg oder geht das in die falsche Richtung?
Diese Frage kann ich beantworten, wenn Sie schreiben, was die einzelnen Bestandteile ihrer Formel bedeuten, bzw. Ihre Gedankengänge dazu darstellen.

KW

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: Übung 12.2

Beitrag von sab »

Prof. Karsten Weihe hat geschrieben:Die Beantwortung dieses Postings wurde ediert, so dass Ihre Frage wieder offen ist?
Sorry, ich hatte vor dem Testat nicht mehr ins Forum geschaut - jetzt ist nichts mehr offen. Danke trotzdem!

Prof. Karsten Weihe hat geschrieben:Das sind sie bei Mergesort auch nicht. Bei Mergesort wächst die Anzahl der Aufrufe exponentiell in der Rekursionstiefe. Entscheidend ist aber bei Mergesort, dass die Rekursionstiefe logarithmisch beschränkt ist und somit die Gesamtzahl Aufrufe sogar linear in der Länge der Sequenz bleibt.
Das stimmt, das hatte ich nicht bedacht - und mein Tutor ist auch auf diese Beschränkung eingegangen! :)

Antworten

Zurück zu „Archiv“