Servus,
ich hänge an einer Aufgabe fest:
Zwei Algorithmen zur Problemlösung (jeweils abh. von einem Parameter p (p>0)
Algo1, rekursiv, durch 8 Teilinstanzen der Größe n/2. Benötigte Gesamtlaufzeit O(n^(p+1))
Algo2, nicht rekursiv. Gesamtlaufzeit O(n^5 + n ^p + log(n))
Für welche Werte von p ist die asymptotische Laufzeit besser, gleich oder schlechter als von Algo2.
Wüsste nicht wie ich da ran gehen soll? Ist es von Bedeutung ob der Algo rekursiv ist? Liebe
Grüße, Vori
Wenn du die Ordnung der jeweiligen Algorithmen gegeben hast, warum erzeugst du dir nicht 2 Graphen, die die Ordnung in Abhängigkeit von n und p darstellen. Am Schnittpunkt der beiden Graphen kannst du das gesuchte p ablesen.
Ob der Algorithmus rekursiv ist, ist für die Aufgabenstellung bei gegebener Ordnung unerheblich.
Gucken wir doch mal nach wo es gleich ist und lösen nach p auf.
n^(p+1) = n^5 + n^p + log(n)
n^p * n = n^5 + n^p + log(n)
n^p * n - n^p = n^5 + log(n)
n^p * (n-1) = n^5 + log(n)
n^p = (n^5 + log(n)) / (n-1)
p = log(zur Basis n) von ((n^5 + log(n)) / (n-1))
Willst Du weiter machen?
Danke euch beiden.
Zu sagen ist noch, dass es eine Klausuraufgabe ist und ein Taschenrechner nicht erlaubt.
@Robert, ich wüsste jetzt nicht wie ich einen Graphen dazu angeben könnte.
@Safrael, danke, das war schonmal sehr hilfreich. Ich wüsste gerade aber nicht wie ich weitermachen soll
Ein Kumpel meinte ich soll das Master Theorem dafür verwenden?
Hi,
ich weiß nicht, wieviel als „bewiesen“ vorausgesetzt werden darf.
Lineare oder polynomielle Laufzeit wächst stärker als logarithmsche Laufzeit. Polynomielle Laufzeit wird vom Grad des Polynoms bestimmt.
Deshalb ist
O(n^5 + n ^p + log(n)) = O(n^5) für p 5.
Damit steht die Lösung schon fast da. Ob das in der Klausur so akzeptiert wird, kann ich Dir aber nicht sagen. Ggf. würde ich die Definition der O-Klasse für eine Rechnung heranziehen.
Gruß,
KHK