Zitat von
alzaimar:
Bei -sagen wir- 1.000.000 unterschiedlichen 4-Tupeln würde eine Binäre Suche 1 Mio * log(1 mio), also ca. 19.000.000 Vergleiche benötigen
Nene, du nimmst gerade O(n*log(n)) an, aber es ist O(log(n)). Bei 1 Mio Einträgen sind nur rund 20 Vergleiche nötig um an das Ziel zu kommen. Halbiere mal 1000000 N mal, und du wirst nach N=20 ein Intervall von ~1,9 erhalten, was mit evtl. noch einem Vergleich mehr einem Fund entspricht. Das ist der Worst-Case.
Noch schneller wirds wie gesagt mit der arithmetischen Suche, die Wikipedia als
Interpolationssuche kennt. Das ungefähre Laufzeitverhalten ist dabei O(log(log(n))), wobei ein Worst-Case mit O(n) auftauchen kann. Um das zu "fixen" kann man sich der
Quadratischen Binärsuche bedienen, die im Wiki leider nur angerissen wird, aber an sich klar wird was da passiert.
O(log(log(n))) ist im Falle von n=1000000 ca. 4,3. Schneller ist dann fast nur noch indizierter Zugriff auf ein Array[Cardinal].
Mich würde tatsächlich interessieren, ob ich da nun grundsätzlich was missverstanden habe.
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)