Алгоритми та структури даних · Middle · Запитання 70 з 75
Чому масиви зазвичай швидше обходити, ніж зв'язні списки, хоча обидва O(n)?
- ✓Правильна відповідь: Елементи масиву лежать поруч у пам'яті, що зручно для кешу процесора
- 2Рушії обходять масиви паралельно на кількох ядрах
- 3Зв'язні списки мусять перевіряти межі на кожному кроці
Пояснення
Big O приховує константи. Суцільна пам'ять завантажується в кеш лініями, а вузли списку, розкидані по купі, дають промахи кешу. Тому на практиці для більшості навантажень виграють масиви.