ftx_cleartel_test

[Camping_RIDER]

Aloha ;)

Falls dich sowas interessiert: solche Grundsätze lernt man in der Vorlesung Algorithmen und Datenstrukturen 1 (soweit ich weiss studierst du ja gerade Mathematik?). Das ist es auch, was Dedlfix mit „YAGNI“ meinte.

...oder in Einführung in die Informatik (das man hört, wenn man wie ich bescheuert ist und neben Mathematik und Physik noch zusätzlich Informatik studiert). ;)

Aber nur dann, wenn O(log n) wirklich zutrifft und nicht durch Overhead des Arrayzugriffs zunichte gemacht wird.

Der Aufwand für einen Array-Zugriff ist, unabhängig von den Kosten, konstant. Die Komplexität für das binary search ist also weiterhin O(log n), auch wenn die Kosten für einen Arrayzugriff grösser würden.

Das kommt auf die interne Implementierung des Array-Zugriffs an. Ich hielt es ursprünglich für möglich, dass der Overhead mit n skaliert; siehe dazu auch die Antwort auf deinen Nachtrag.

Grüße,

RIDER