Laufzeit Dijkstra

[Matthias Gubisch]

Hallo zusammen

ich häng jezt schon seit einiger Zeit an einen Problem.

Und zwar soll ich beweisen, dass Dijkstra's Algorithmus eine Laufzeit von O(m log2+m/n(n)) hat wenn für die Implementierung d-Heaps verwendet werden und das d geeignet gewählt wird.

Ich probier hier schon ein paar Stunden rum und komm auf nix, vielleicht hat ja jemand wenigstens einen Ansatz?

[eXile]

\($O(m \log2+m/n(n))$\)

Was sind \($n$\) und \($m$\)? Und wovon wir der erste Logarithmus gebildet? Und vorallem: Was ist \($n(n)$\)? Ansonsten mein erster Ansatz: Oh boy here we go again! (Seite Nummer 41.)

Nachtrag:
Ahh … ich glaube so langsam dämmerts mir. Meintest du:

\($O(m \cdot \log_{2 + \frac{m}{n}} (n))$\)

[Matthias Gubisch]

Genau das hab ich gemeint.
Das Dokument kannte ich schon, das Problem ist dass ich irgendwie nicht draufkomme wie ich den Beweiß führen muss
Irgendwie seh ich da glaub ich den Wald vor lauter Bäumen nicht...