Асимптотический анализ и нотация Big O: Полное руководство

Введение: Почему секунды обманчивы?

Физическое время работы программы в миллисекундах зависит от архитектуры процессора, языка реализации, компилятора и загруженности ОС. Чтобы сравнивать алгоритмы независимо от «железа», в Computer Science используют асимптотический анализ и нотацию Big O.

Big O описывает не точное время работы в секундах, а закон, по которому растёт число базовых операций программы при увеличении размера входных данных $N$ к бесконечности ($N \to \infty$).

---

Формальные математические обозначения: O, $\Omega$, $\Theta$, o, $\omega$

1. Нотация Big O (Верхняя оценка / Worst-Case Bound)

Формально: существуют положительные константы $c > 0$ и $n_0 \ge 1$, такие что для всех $n \ge n_0$:

Предельное определение: $\limsup_{n \to \infty} \frac{f(n)}{g(n)} < \infty$.

2. Нотация Big $\Omega$ (Нижняя оценка / Best-Case Bound)

Формально: существуют константы $c > 0$ и $n_0 \ge 1$, такие что:

3. Нотация Big $\Theta$ (Точная оценка / Tight Bound)

Формально: существуют константы $c_1, c_2 > 0$ и $n_0 \ge 1$, такие что:

4. Строгие оценки: Малое $o$ и Малое $\omega$

$f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$ ($f$ растёт строго медленнее $g$).

$f(n) = \omega(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$ ($f$ растёт строго быстрее $g$).

---

Иерархия классов сложности