Binary Insertion Sort vs. Insertion Sort
- Themenstarter Dolphon
- Beginndatum
jokey2
Erfahrenes Mitglied
Ich weiß zwar nicht, auf welche Implementierungen der Algorithmen du dich beziehst, aber wer behauptet das?
Im Allgemeinen ist die Binärsuche schneller, da von der Ordnung log
, Lineare Suche hat die Ordnumg n.
Bei sehr kleinen Anzahlen von elementen unterscheiden sich die Zugriffszeiten nur wenig, je größer aber die Liste, desto größer der Unterschied.
Es gibt natürlich Einzelfälle, in denen die lineare Suche schneller ist.
Z.B. wenn das erste Element gesucht wird, wäre die lineare suche natürlich schneller, da sie beim ersten Element beginnt.
In einer statistischen Verteilung der zu suchenden Elemente ist IMHO Binärsuche immer schneller.
Im Allgemeinen ist die Binärsuche schneller, da von der Ordnung log
, Lineare Suche hat die Ordnumg n.Bei sehr kleinen Anzahlen von elementen unterscheiden sich die Zugriffszeiten nur wenig, je größer aber die Liste, desto größer der Unterschied.
Es gibt natürlich Einzelfälle, in denen die lineare Suche schneller ist.
Z.B. wenn das erste Element gesucht wird, wäre die lineare suche natürlich schneller, da sie beim ersten Element beginnt.
In einer statistischen Verteilung der zu suchenden Elemente ist IMHO Binärsuche immer schneller.
Matthias Reitinger
ɐɯıǝɹ
Hallo,
Suchen ? Sortieren! Binary Insertion Sort ist deshalb nicht zwingend schneller, weil das Verschieben der Elemente beim Einfüge-Vorgang im Durchschnitt immer noch quadratische Komplexität besitzt. Der Einfüge-Vorgang dominiert also den Such-Vorgang, sodass die Suche (asymptotisch) nicht in's Gewicht fällt. Die Komplexität im besten Fall (bereits sortierte Sequenz) verschlechtert sich bei Binary Insertion Sort sogar auf ?(n log n) gegenüber ?(n) beim normalen Insertion Sort.
Grüße,
Matthias
Suchen ? Sortieren! Binary Insertion Sort ist deshalb nicht zwingend schneller, weil das Verschieben der Elemente beim Einfüge-Vorgang im Durchschnitt immer noch quadratische Komplexität besitzt. Der Einfüge-Vorgang dominiert also den Such-Vorgang, sodass die Suche (asymptotisch) nicht in's Gewicht fällt. Die Komplexität im besten Fall (bereits sortierte Sequenz) verschlechtert sich bei Binary Insertion Sort sogar auf ?(n log n) gegenüber ?(n) beim normalen Insertion Sort.
Grüße,
Matthias
