Laufzeit mit Entfernungstabelle verkürzen?

[Vinzenz Mai]

Hallo Matti,

Würde ich so erstmal nicht aussagen. Die im OP angegebene Formel kann IMHO in O(1) berechnet werden. Das Nachschlagen wird, wenn mich nicht alles täuscht, mit O(log N) zu Buche schlagen.

ja und :-) Soviel zur Theorie.

Lieber Gast: bist du sicher, dass der angegebene Ausdruck langsam ist?

klar ist der Ausdruck langsam. Und warum spielt O(1) in der Praxis keine Rolle? Warum nutzt man Quicksort, was im Original miserabel langsam sein *kann*?
Warum hat man bis vor ca. 30 Jahren noch mit Logarithmentafeln gearbeitet?
Warum haben früher exzellente Mathematiker einen Großteil ihrer Arbeit in das Erstellen solcher Tafeln gesteckt? Weil Nachschlagen schneller sein kann als Berechnen :-)

Haufenweise trigonometrische Funktionen, die *sehr* aufwendig sein werden.

Falls meine Vermutung mit O(1) falsch sein sollte, ist der Ansatz, welchen du wählst, sicherlich nicht allzu falsch.

Ich gehe von einer dünn besetzten Matrix aus. Da schlägt die Praxis die Theorie. Sprich: O(log N) mit knappem inneren Code ist schneller als O(1).

Freundliche Grüße

Vinzenz