Hier hilft wieder ein Exkurs in Komplexitätsberechnung: Sei LL die (doppelt) verkettete Liste (Linked List) und DA das dynamische Array;
Anhängen:
LL = O(1)
VA = O(1)
(VA einige Takte schneller, da nur ein Speicherzugriff, LL muss noch die Zeiger aktualisieren)
Sortiert Einfügen:
LL = O(n)
VA = O(n) (O (n log n) für binary search und O(n) für das 'Platz machen', also Verschieben)
(tendentiell VA schneller, da das verschieben des Arrays zum 'Platzmachen' sehr schnell geht)
Löschen:
LL = O(n)
VA = O(n)
(tendentiell VA schneller, da das verschieben des Arrays zum 'Platzmachen' sehr schnell geht)
Sortieren:
Beide gleich, optimal ist O(n log n)
Wenn man das dynamische Array jeweils in seiner Größe verdoppelt, kann man diesen Zeitaufwand vernachlässigen.
Was bedeutet das?
O(1) = Die Operation ist immer gleich schnell, unabhängig von der Anzahl der Elemente.
O(n) = Zeitaufwand steigt linear: Verdoppelung der Listengröße => Verdoppelung des Zeitaufwandes
O(n log n) [log hier log2] = Zeitaufwand steigt logarithmisch. Verdoppelung der Listengröße => ca. 10% höherer Zeitaufwand.
...
Zitat von
helga5:
Im Buch "Grundlagen und Profiwissen" von Walter Doberenz und Thomas Kowalski ....Shellsort ist am schnellsten.
Quicksort wurde nicht getestet? Merkwürdig.
Unterm Strich verwende ich verkettete Listen nicht mehr (die haben keinerlei Vorteile). Für einfache Listen verwende ich ein dynamisches Array oder eine T(String)List, wenn mir die Performance nicht so wichtig ist. Ansonsten eine Hashmap oder gleich eine gute
DB.
Wer Listen mag, sollte aber eine Skiplist verwenden, die sind einfach sauschnell, praktisch und nur minimal langsamer als eine (gute) Hashmap. Leider ist der Speicherbedarf pro Element ziemlich hoch (ca. 32 Byte für Hilfszeiger).
Zitat von
hanselmansel:
Schuss ins Blaue
Wird ein dynamisches Array nicht intern selbst über verkettete Listen realisiert?
Und voll daneben geschossen.
