Algorithmen und Datenstrukturen · Middle · Frage 70 von 75
Warum lassen sich Arrays meist schneller durchlaufen als verkettete Listen, obwohl beides O(n) ist?
- 1Array-Elemente liegen beieinander im Speicher, was dem CPU-Cache passt
- 2Engines durchlaufen Arrays parallel auf mehreren Kernen
- 3Verkettete Listen müssen bei jedem Schritt Grenzen prüfen
Antwort zeigen
Richtige Antwort: Array-Elemente liegen beieinander im Speicher, was dem CPU-Cache passt
Erklärung
Die O-Notation verdeckt Konstanten. Zusammenhängender Speicher wird in Cache-Zeilen vorgeladen; über den Heap verstreute Listenknoten verursachen Cache Misses. Deshalb gewinnen Arrays in der Praxis bei den meisten Lasten.