📊 Асимптотический анализ алгоритмов: O(n log n) и почему это важно

Новая статья — о том, как теория пределов превращается в инструмент инженера.

Внутри:
🔹O, Ω, Θ: как сравнивать скорость роста функций;
🔹почему константы игнорируются, а порядок роста — нет;
🔹базовая шкала сложностей: от O(1) до O(n!);
🔹мастер-теорема для рекуррентностей T(n) = aT(n/b) + f(n);
🔹амортизационный анализ: O(1) для динамического массива без вероятностей;
🔹нижние границы: сортировка не быстрее Ω(n log n), а Страссен ломает кубический барьер.

Статья объясняет, как выбирать алгоритм до запуска кода и где кончается инженерия.

Преждевременная оптимизация — корень всех зол. Отсутствие асимптотического анализа — корень всех задержек.