Что значит O(n log n) и почему быстрая сортировка именно такая?
Везде пишут, что хорошие сортировки работают за O(n log n). Я понимаю O(n) — это «пройти один раз». А откуда тут берётся log n и почему это считается быстро? Объясните на пальцах.
3 ответа
Грубо: log n — это сколько раз можно поделить n пополам, пока не дойдёшь до 1. Для миллиона элементов log2(n) ≈ 20. Хорошие сортировки (быстрая, слиянием) на каждом «уровне деления» проходят все n элементов, а уровней этих как раз ~log n. Отсюда n * log n.
Сравни: наивная сортировка (пузырёк) сравнивает каждый с каждым — это nn. Для миллиона элементов nn = триллион операций, а n*log n ≈ 20 миллионов. Разница в 50 000 раз — вот почему n log n считают «быстро».
Главное: log растёт ОЧЕНЬ медленно. Удвоил данные — log вырос всего на 1. Поэтому n log n почти как линейный по ощущениям, просто чуть-чуть хуже.
Это нижняя граница для сортировки сравнениями — быстрее, чем n log n, на сравнениях в общем случае нельзя, доказано.
