Нотации Big-O, Ω и Θ

Асимптотические обозначения позволяют сравнивать скорость роста функций. Мы отбрасываем константы и малые слагаемые и оставляем главное.

Три обозначения

• O(g) — верхняя оценка: f растёт не быстрее g.
• Ω(g) — нижняя оценка: f растёт не медленнее g.
• Θ(g) — точная оценка: f и g растут одинаково.

Функция 3n² + 5n + 7 — это O(n²), Ω(n²) и значит Θ(n²). Она также O(n³), но это слабая оценка.

Формальное определение

• f(n) = O(g(n)), если существуют c > 0 и n0, такие что f(n) ≤ c · g(n) для всех n ≥ n0.
• f(n) = Ω(g(n)), если существуют c > 0 и n0, такие что f(n) ≥ c · g(n) для всех n ≥ n0.
• f(n) = Θ(g(n)), если верны и O, и Ω.

Знак «=» здесь не равенство, а «принадлежит классу».