Algorytmy i struktury danych · Middle · Pytanie 70 z 75
Dlaczego tablice zwykle przechodzi się szybciej niż listy wiązane, choć oba to O(n)?
- ✓Poprawna odpowiedź: Elementy tablicy leżą obok siebie w pamięci, co sprzyja cache procesora
- 2Silniki przechodzą tablice równolegle na kilku rdzeniach
- 3Listy wiązane muszą sprawdzać granice na każdym kroku
Wyjaśnienie
Big O ukrywa stałe. Ciągła pamięć jest ładowana do cache liniami, a węzły listy rozsiane po stercie powodują chybienia cache. Dlatego w praktyce tablice wygrywają w większości zastosowań.