in sortierte liste sortiert einfügen

[Medium]

Zitat von wikipedia:

Therefore, the total expected cost of a search is O(log(1/p, n))/p which is O(log(n)) when p is a constant.

Ich wage die Behauptung, dass es hier wieder ganz auf den konkreten Fall ankommt ob sich eine Skip-List lohnt. Ein nicht unwichtiger Teil des von dir zitierten ist: "für beliebige Daten deren Verteilung man überhaupt nicht einschätzen kann", das heisst ohne jede Kenntnis der inneren Struktur der Daten. Für spezifische Sets lassen sich fast immer angepasste Verfahren finden, der TE gibt hierüber aber leider keine Auskunft. Also muss man doch vom generischen Fall ausgehen oder? In diesem sind die beiden Verfahren aber immerhin gleich gut. Skiplisten bedürften lediglich etwas mehr Implementierungsaufwand oder Fremdklassen, da Delphi keine mitbringt.
Ein Nachteil der Skiplisten ist aber sicherlich der Strukturelle Overhead, sowie redundante Elemente, wodurch man u.U. in die Situation geraten kann dass man mehr Speicher für eine vergleichbare Performance verbrät - und joa, wenn wir über Listen der Größe sprechen dass sich optimierte Suchverfahren lohnen, wird Speicher schon weniger unendlich =] Dem TE wird, wenn er wirklich das Optimum haben will, nicht viel anderes bleiben als alle in Frage kommenden Algos zu basteln, und sie an seinem Echt-Daten Set zu testen. (Ich persönlich habe die besten Erfahrungen mit Interpolationssuche gehabt, aber das war halt auch wieder ein Fall in dem sie einfach gut zu den Daten gepasst hat.)