# Искусство игнорировать лишнее: как Big O помогает сравнивать Swap Sort и Merge Sort

Источник: https://www.youtube.com/watch?v=6dQQAn4L24s
Канал: MIT OpenCourseWare
Опубликовано: 22.07.2025

---

В лекции MIT OpenCourseWare профессор Закари Абель завершает обсуждение математических сумм и переходит к асимптотическому анализу — фундаментальному инструменту оценки алгоритмов. Наглядная демонстрация с физическими блоками и разбор классических функций роста позволяют понять, почему в Computer Science принято игнорировать константы и как математически строго сравнивать эффективность программного кода.

## 🧱 Головоломка с блоками и гармонические числа
[[JUMP:0:38]]

Закари Абель начинает занятие с демонстрации физического эксперимента: как далеко можно выдвинуть стопку блоков за край стола, чтобы она не упала [0:51]. Используя «жадную стратегию» — сдвиг каждого верхнего слоя до центра масс — профессор показывает, что верхний блок может полностью находиться вне проекции стола [2:49]. По словам Абеля, эта стратегия является математически оптимальной, хотя физическая реализация ограничена масштабами [3:38].

Математическая модель этого процесса описывается следующими фактами:

*   Первый блок выступает на 1/2 своей длины.
*   Второй — на 1/4, третий — на 1/6, и так далее.
*   Сдвиг n-го блока составляет $1/2n$ [4:40].
*   Общее расстояние выноса стопки из n блоков равно $1/2 \times H_n$, где $H_n$ — n-е гармоническое число [5:11].

Гармоническое число $H_n$ определяется как сумма последовательности $1 + 1/2 + 1/3 + \dots + 1/n$. Для оценки этой суммы Абель применяет интегральный метод, доказывая, что значение $H_n$ зажато между $\ln(n) + 1/n$ и $\ln(n) + 1$ [7:52]. Профессор отмечает забавный физический парадокс: чтобы выдвинуть стопку блоков на расстояние 10 длин от стола, потребуется около 400 миллиардов блоков [9:06]. Высота такой стопки в 40 раз превысит расстояние до Луны, что делает задачу математически возможной, но физически невыполнимой [9:20].

## 📈 Асимптотическая эквивалентность и факториалы
[[JUMP:10:03]]

Для более точного описания приближений вводится понятие асимптотической эквивалентности ($\sim$). По определению Абеля, функции $f(n)$ и $g(n)$ асимптотически эквивалентны, если предел их отношения при $n$, стремящемся к бесконечности, равен 1 [10:32]. Так, гармоническое число $H_n$ асимптотически эквивалентно натуральному логарифму $\ln(n)$ [12:06].

Этот же подход применим к анализу произведений, таких как факториал ($n!$). Профессор объясняет, что анализ произведений проще всего проводить, превращая их в суммы через логарифмирование [12:47]:

*   $\ln(n!) = \ln(1) + \ln(2) + \dots + \ln(n)$.
*   Применяя интегральные оценки к сумме логарифмов, можно получить границы для $n!$ через экспоненту [15:50].

Для более точных вычислений Абель рекомендует использовать формулу Стирлинга, согласно которой $n!$ асимптотически эквивалентен выражению $\sqrt{2\pi n} \cdot (n/e)^n$ [17:54]. Существует и еще более строгая оценка, включающая множитель $e^{1/12n}$, которая позволяет оценивать погрешность даже для небольших значений $n$ [19:23].

## ⚖️ Сравнение алгоритмов: Swap Sort против Merge Sort
[[JUMP:20:19]]

Переходя к практическому применению математики в IT, профессор сравнивает два алгоритма сортировки:

1.  **Swap Sort (сортировка обменами):** Количество операций в худшем случае составляет примерно $n^2/2 - n/2$ [22:03].
2.  **Merge Sort (сортировка слиянием):** Количество сравнений ограничено величиной $n \log_2 n - n + 1$ [22:48].

Абель демонстрирует «ай-трекер» (фокус внимания) разработчика при взгляде на эти формулы. По его мнению, при работе с «большими данными» (миллионы или миллиарды элементов) второстепенные члены и константы становятся «ошибкой округления» [24:56]. 

Причины, по которым константы игнорируются в асимптотическом анализе:

*   Разные единицы измерения: один и тот же алгоритм можно оценивать в секундах, циклах процессора или количестве инструкций [28:09]. 
*   Смена оборудования: на более быстром процессоре время выполнения уменьшится в фиксированное количество раз, но характер зависимости (например, квадратичный) останется неизменным [28:47].
*   Когнитивная нагрузка: знать, что население США составляет «около 330 миллионов», полезнее для общего понимания, чем оперировать точным числом до единиц [30:09].

## 🅾️ Математика Big O: правила и определения
[[JUMP:32:01]]

Центральной темой лекции становится нотация Big O ($O$). Абель подчеркивает, что интуитивно запись $f(n) \in O(g(n))$ означает, что функция $f$ растет не быстрее, чем $g$, если игнорировать константы и малые значения $n$ [32:53].

Формальное определение Big O требует существования двух положительных констант — $C$ и $n_0$ — таких, что для всех $n \ge n_0$ выполняется неравенство $|f(n)| \le C \cdot |g(n)|$ [34:09]. Профессор поясняет роль этих констант:

*   $C$ позволяет игнорировать масштабирование функций [36:57].
*   $n_0$ позволяет игнорировать аномальное поведение алгоритма на малых входных данных [35:16].

Примеры применения нотации:

*   Линейная функция $n$ является $O(n^2)$, так как при любом $C \ge 1$ и $n \ge 1$ квадрат растет быстрее [38:06].
*   Квадратичная функция $n^2$ не является $O(n)$, так как никакой множитель $C$ не позволит прямой обогнать параболу на бесконечности [42:31].
*   Константы и младшие члены в многочленах (например, $n^2 + 3n + 7$) просто «поглощаются» константой $C$ при переходе к $O(n^2)$ [44:22].

## 📋 Иерархия асимптотических символов
[[JUMP:47:14]]

Для удобства анализа Абель предлагает использовать «предельный тест»: если предел отношения $f(n)/g(n)$ конечен, то $f \in O(g)$ [48:25]. Если же предел равен бесконечности, то $f$ растет строго быстрее [47:51]. Однако он предупреждает, что если предел не существует (функция колеблется), тест становится неинформативным [50:02].

Помимо Big O, профессор вводит другие важные символы:

1.  **Big Omega ($\Omega$):** Обратное понятие к Big O. Означает, что функция растет не медленнее заданной [56:18].
2.  **Theta ($\Theta$):** Означает, что функции растут с одинаковой скоростью с точностью до константы. Это одновременно и $O$, и $\Omega$ [59:24].
3.  **Little o ($o$):** Означает, что функция $f$ значительно меньше $g$ (предел их отношения равен 0) [1:06:42].
4.  **Little omega ($\omega$):** Означает, что $f$ значительно больше $g$ (предел равен бесконечности) [1:07:50].

Абель подчеркивает разницу между асимптотической эквивалентностью ($\sim$) и нотацией $\Theta$: первая требует, чтобы константы совпадали (отношение равно 1), вторая разрешает любой постоянный множитель [1:01:14].

## ⚠️ Ловушка индукции в асимптотике
[[JUMP:1:10:01]]

В завершение лекции Закари Абель приводит пример «ложного доказательства», чтобы предостеречь студентов от совместного использования индукции и Big O [1:10:22]. 

Он демонстрирует шуточное доказательство того, что $2^n \in O(1)$ (экспонента якобы является константой):

*   База: $2^0 \in O(1)$ — верно.
*   Шаг: Если $2^n \in O(1)$, то $2^{n+1} = 2^n + 2^n \in O(1) + O(1) = O(1)$ [1:12:14].

Ошибка в том, что индукция доказывает утверждение для каждого конкретного числа $n$, подтверждая лишь то, что каждая отдельная степень двойки — это какое-то константное число [1:14:52]. Однако асимптотика анализирует функцию целиком во всем её диапазоне. Профессор призывает «сделать шаг назад», если вы пытаетесь использовать индукцию для доказательства асимптотических свойств функции, так как эти методы плохо смешиваются [1:15:36].