Алгоритми та структури даних · Senior · Запитання 30 з 75
Чому алгоритм O(n log n) може програти O(n²) на реальних даних?
- ✓Правильна відповідь: Big O приховує константи, а для малих n вони домінують
- 2Алгоритми O(n²) компілюються з більшими оптимізаціями
- 3O(n log n) справджується лише для n - степеня двійки
Пояснення
Сортування вставками обганяє злиття на кількох десятках елементів завдяки мізерним накладним витратам і дружньому до кешу доступу. Тому Timsort та introsort переходять на вставки для малих серій.