Dijkstra - Laufzeit für dinären Heap

26.11.2005, 12:36

DerUnwissende

Dijkstra - Laufzeit für dinären Heap

Hi,
ich habe ein Problem mit der Berechnung eines optimalen Wertes für einen dinären Heap. Als dinärer Heap ist hier ein Baum gemeint, dessen Knoten jeweils d Kinder haben können (die weiteren Eigenschaften des Heap sind unwichtig).
Abhängig von der Anzahl der Knoten n soll nun d optimiert werden.
Für den Dijkstra-Algorithmus (realisiert mittels eines solchen Heaps) komme ich auf n Operationen mit Laufzeit $\begin{eqnarray*} d \cdot log_{d} n \end{eqnarray*}$ und auf m Operationen mit Laufzeit $\begin{eqnarray*} log_{d} n \end{eqnarray*}$ .

Damit hätte ich eine Laufzeit in Abhängigkeit von d gegeben durch
$\begin{eqnarray*} f(d) = n \cdot d \cdot log_{d} n + m \cdot log_{d} \end{eqnarray*}$

Und zur Minimierung würde ich jetzt die Ableitung 0 setzen. Nur leider komme ich beim ableiten nicht wirklich auf den richtigen Weg. Hier mal mein Ansatz:
$\begin{eqnarray*} f(d) = n \cdot d \cdot {\frac {log_{n} n}{log_{n} d}} + m \cdot {\frac {log_{n} n}{log_{n} d}} \end{eqnarray*}$
$\begin{eqnarray*} f'(d) = n \cdot d \cdot {\frac {-1}{d \cdot ln n \cdot (log_{n} d)^{2}}} + {\frac {n}{log_{n} d} + m \cdot {\frac {-1}{d \cdot ln n \cdot (log_{n} d)^{2}}}} \end{eqnarray*}$
$\begin{eqnarray*} = {\frac {-n}{log_{n} d \cdot ln n}} + n + {\frac {-m}{d \cdot log_{n} d \cdot ln n}} \end{eqnarray*}$
$\begin{eqnarray*} f'(d) = 0 \Leftrightarrow -n = { \frac {-n} {log_{n} d \cdot ln n}} + {\frac {-m}{d \cdot log_{n} d \cdot ln n}} \end{eqnarray*}$
$\begin{eqnarray*} n \cdot ln n = {\frac {n}{log_{n} d}} + {\frac{m}{d \cdot log_{n} d}} \end{eqnarray*}$

Ja, und hier finde ich keinen guten Ansatz wie ich das nach d auflösen kann. Aber vielleicht mache ich ja schon davor irgendwas völlig falsch? Wäre für jeden Tipp dankbar, also schon mal danke im Vorraus

Gruß Der Unwissende

26.11.2005, 13:44

Auf diesen Beitrag antworten »

Ich hab mir nicht alles durchgelesen, weil mir diese umständliche Art widerstrebt: Wieso zum Teufel verwendest du das zwar richtige, aber zum Ableiten äußerst umständliche

$\begin{eqnarray*} \log_d x = \frac {\log_{n} x}{\log_{n} d} \end{eqnarray*}$

und nicht gleich den natürlichen Logarithmus

$\begin{eqnarray*} \log_d x = \frac{\ln x}{\ln d} \end{eqnarray*}$

?

26.11.2005, 15:08

DerUnwissende

Auf diesen Beitrag antworten »

Zitat:

Wieso zum Teufel verwendest du das zwar richtige, aber zum Ableiten äußerst umständliche
$\begin{eqnarray*} log_{d} x = \frac {log_{n} x} {log_{n} d} \end{eqnarray*}$

Ich benutze diese Schreibweise, weil ich mit n die Anzahl der Knoten bezeichnet habe ( $\begin{eqnarray*} n \neq e \end{eqnarray*}$ ).
Sorry, die Benennungen sind halt etwas aus der Informatik, da verwendet man halt gerne n für die Anzahl der Knoten, hätte ich wohl nochmal zu schreiben sollen. Falls irgendwas anderes umständlich geschrieben ist, liegt das eher an meinem fehlenden Blick was man zusammenfassen kann

Gruß Der Unwissende

26.11.2005, 15:29

Auf diesen Beitrag antworten »

Ich hab ja nicht geschrieben, dass es falsch ist. Es ist nur unheimlich umständlich hinsichtlich des Ableitens, und daher auch fehleranfällig.

$\begin{eqnarray*} (\ln x)' = \frac{1}{x} \end{eqnarray*}$ schreit doch geradezu danach, den natürlichen Logarithmus zu verwenden.

Wie auch immer, deine letzte Gleichung kann in

$\begin{eqnarray*} n = \frac {n}{\ln d} + \frac{m}{d \ln d} \end{eqnarray*}$

umgeschrieben werden, dass müsste stimmen. Umgeschrieben heißt das

$\begin{eqnarray*} d (\ln d-1) = \frac{m}{n} \end{eqnarray*}$

Mit der Substitution $\begin{eqnarray*} x=\ln d-1 \end{eqnarray*}$ wird daraus

$\begin{eqnarray*} xe^x = \frac{m}{ne} \end{eqnarray*}$

mit der Lösung $\begin{eqnarray*} x=W\left(\frac{m}{ne}\right) \end{eqnarray*}$ , also $\begin{eqnarray*} d=\exp\left\{ W\left(\frac{m}{ne}\right)+1\right\} \end{eqnarray*}$ mit der LambertW-Funktion $\begin{eqnarray*} W \end{eqnarray*}$ .

26.11.2005, 16:13

DerUnwissende

Auf diesen Beitrag antworten »

Super, danke!!! Wäre ich wohl ohne Hilfe nie drauf gekommen (kenne diese Funktion ja nichtmal). Freude

Neue Frage »

Antworten »

Dijkstra - Laufzeit für dinären Heap

Verwandte Themen