Ableitung von Quicksort-Rechenzeitfunktion für Anstieg in bestimmten Punkt

02.07.2020, 11:25	3xplor3r	Auf diesen Beitrag antworten »
Ableitung von Quicksort-Rechenzeitfunktion für Anstieg in bestimmten Punkt Moin, ich habe folgende Rechenzeitfunktion für den mittleren Elementzugriff abhängig von der Problemgröße, also die Anzahl zu sortierender Elemente des Quicksort-Algorithmus, vorliegen. $\begin{eqnarray} \bar{f}(n) = 1,386n \times ld(n) - 2,846n + 1,386 \times ld(n) + 1,154 \end{eqnarray}$ In der Lösung zur Übungsaufgabe wird für $\begin{eqnarray} n = 1000 \end{eqnarray}$ eine Anstiegsrate von $\begin{eqnarray} 16,98 \end{eqnarray}$ angegeben. Als vorbildliche Studierende, die wir alle sind, wollte ich das Ergebnis nachbilden. Um den Anstieg im Punkt (1000, 10982), 10982 ist die Anzahl der mittleren Zugriffe für $\begin{eqnarray} n = 1000 \end{eqnarray}$ , die Quicksort benötigt, zu berechnen, wollte ich die erste Ableitung bilden. $\begin{eqnarray} \bar{f}(n)' = 1,386 \times ld(n) + \frac{1,386n}{n \times ln(2)} + \frac{1,386}{n \times ln(2)} - 2,846 \end{eqnarray}$ Den ersten Term habe ich mit der Produktregel nach $\begin{eqnarray} n \end{eqnarray}$ abgeleitet. Der zweite Term verbleibt als Konstante am Ende der Funktion. Der dritte Term ist gemäß $\begin{eqnarray} d/dn\left(ld(n)\right) = \frac{1}{n \times ln(2)} \end{eqnarray}$ nach $\begin{eqnarray} n \end{eqnarray}$ abgeleitet. Der letzte Term fällt bekanntlich weg. Ist das Zwischenergebnis so korrekt? Wenn ich damit rechne, komme ich auf $\begin{eqnarray} 12,96 \end{eqnarray}$ anstatt der angegebenen $\begin{eqnarray} 16,98 \end{eqnarray}$ . Auch mit der Hand am Arm, (999, 10969) und (1000, 10982), die Werte sind gerundet, entspricht der Anstieg $\begin{eqnarray} 12,96 \end{eqnarray}$ , was hoffentlich darauf schließt, dass meine Ableitung korrekt ist. Was ebenfalls auffällt, ist, dass die in der Lösung angegebenen Werte mit zunehmender Problemgröße kleiner werden. So ist für $\begin{eqnarray} n = 10000 \Rightarrow 14,18 \end{eqnarray}$ , $\begin{eqnarray} n = 100000 \Rightarrow 12,96 \end{eqnarray}$ und $\begin{eqnarray} n = 1000000 \Rightarrow 12,28 \end{eqnarray}$ angegeben. Meine Werte sind hingegen $\begin{eqnarray} n = 10000 \Rightarrow 17,57 \end{eqnarray}$ , $\begin{eqnarray} n = 100000 \Rightarrow 22,17 \end{eqnarray}$ und $\begin{eqnarray} n = 1000000 \Rightarrow 26,77 \end{eqnarray}$ , werden also immer größer. Hat jemand eine Idee, warum sich die Ergebnisse unterscheiden? Hej Hej [Dänisch für Tschüß ]
02.07.2020, 11:35	HAL 9000	Auf diesen Beitrag antworten »
Es sollte zunächst geklärt werden, was der Aufgabensteller unter Anstiegsrate versteht - allem Anschein wohl nicht einfach nur $\begin{eqnarray} \bar{f}'(n) \end{eqnarray}$ .
02.07.2020, 16:43	Krombopulus	Auf diesen Beitrag antworten »
Also deine Ableitung ist wie du schon selbst sagst korrekt (ld=log_2?), du hast sie ja sogar mit finiten Differenzen überprüft. Ein interessanter Zufall ist auch, dass du für f'(x=1000) den Wert rausbekommst, den die Lösung für f'(x=100000) angibt. Entweder ist es wie HAL sagt und die Rate ist anders definiert. Vielleicht hat aber auch der Aufgabensteller, Aufgabe oder Lösung angepasst ohne das jeweils andere anzupassen. Das kann schon mal passieren wenn man Übungsblätter überarbeitet. Aber dafür gibt es ja fleißige Studenten, die dann mit "Entschuldigen Sie Bitte" in die Vorlesung eingreifen. Und das ist auch gut so!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »