Algorithmus zu einer Suchfunktion

[Rolf b]

Ok.

Schlaufuxige, blitzgescheite Algorithmen dazu gibt's sicher mengenweise, frag Donald, Robert oder Niklaus. Roberts Buch habe ich noch aus Ausbildungzeiten hier stehen, Donald und Niklaus mal irgendwann aus der Bibliothek geliehen gehabt.

Problem bei den dreien ist nur, dass deren Algorithmen gerne auf geringe Komplexität optimieren, aber dafür Sockelaufwand mitbringen. Du bekommst dann einen blitzgescheiten Suchalgorithmus, und einen seitenlangen informationstheoretischen Beweis, dass seine Laufzeitkomplexität $$O(\log{(n-3,51)})$$ beträgt. Deine naive Suche dackelt dagegen mit $$O(n)$$ daher, hat aber den Vorteil, längst fertig zu sein, bis das Obergenie sich seine Strategie zurechtgelegt hat. Dafür ist das Obergenie dann bei Datenmengen mit 10000 Einträgen unglaublich fix. Beeindruckend, aber im konkreten Fall nutzlos.

Oder anders formuliert: Ich kaufe kein Sägewerk, um ein Stück von einer Dachlatte abzuschneiden. Für kleine zu durchsuchende Listen wird deine naive Suche immer hinreichend sein. Um sie zu optimieren, muss man aber Rahmenbedingungen kennen, sonst geht die Optimierung fehl. Selbst eine Trivialität wie "Sortiere nach Beginnzeit und führe statt einer sequenziellen Suche eine binäre Suche aus" bringt nur was, wenn Du Einschränkungen für überlappende Intervalle machst. Andernfalls kann dir irgendein ewig langes Intervall aus frühen Morgenstunden böse den Abend verderben.

Rolf