Конспект: асимптотика

Понятия

O(g) - верхняя граница «не быстрее». f = O(g), если есть c > 0 и n₀, такие что f(n) ≤ c·g(n) для всех n ≥ n₀.

Ω(g) - нижняя граница «не медленнее». Зеркало O: c·g(n) ≤ f(n) с какого-то n₀.

Θ(g) - коридор «ровно как g»: c₁·g(n) ≤ f(n) ≤ c₂·g(n) с какого-то n₀. f = Θ(g) тогда и только тогда, когда f = O(g) И f = Ω(g).

c и n₀ - множитель и порог, которые предъявляют, доказывая принадлежность. c глотает константу, n₀ - поведение на малых входах.

Что унести

Доказать принадлежность классу - предъявить конкретные c и n₀ и проверить неравенство. Опровергнуть - показать, что никакая пара не годится (так n² не является O(n): n² ≤ c·n требует n ≤ c, а n неограничен).

Θ доказывают двумя границами: потолок (c₂) и дно (c₁). Многочлен всегда Θ от старшего члена: потолок - множитель побольше, дно - сам множитель старшего.

Знак в определении нестрогий (≤, ≥): граничное равенство засчитывается. Строгое сравнение - классическая ошибка на единицу в пороге n₀.

Три рабочих правила из определения: множитель-константа выбрасывается (c·f = Θ(f)); сумма равна старшему слагаемому (f + g = Θ(max(f, g))); независимая вложенность перемножается.

Лестница порядков: 1 < log n < n < n·log n < n² < n³ < 2ⁿ < n!. Порядок фрагмента - его самая дорогая часть. Граница n³ | 2ⁿ - это граница «выполнимо | невыполнимо»: показатель бьёт основание.

O - когда известен только потолок (гарантия «не хуже»); Θ - когда известны обе стены (честное сравнение).

Ловушки джокера

Прочитал O как точное значение. O(n²) значит «не быстрее квадрата», а не «ровно квадрат». Линейный алгоритм честно O(n²). Точное - это Θ.

Спутал O с худшим случаем. O описывает рост функции; какую функцию берут (худшего, лучшего, среднего случая) - отдельный вопрос. Бывает «в лучшем случае O(n)».

Повесил Θ на алгоритм без указания случая. «Быстрая сортировка - Θ(n·log n)» неверно: в худшем случае Θ(n²). Правильно - «в среднем Θ(n·log n), в худшем O(n²)».

Взял строгий знак вместо нестрогого. Определение через ≤/≥. На границе, где f = c·g, строгое < пропустит точку и сдвинет n₀ на единицу.

Сложил порядки вместо максимума. n + n² это Θ(n²), а не Θ(n³). Складываются функции; перемножаются только вложенные циклы, а не идущие подряд.

Недооценил экспоненту. 2ⁿ кажется «немного больше n²», а при n = 50 это уже квадриллион. 2ⁿ и n! растут от показателя и бьют любую степень n.

Проверь себя

Что надо предъявить, чтобы доказать f = O(g), и что - чтобы опровергнуть?

Почему n = O(n²) истинно, а n² = O(n) - нет?

Как из O и Ω получается Θ и почему одного O для Θ мало?

Почему в определении знак нестрогий и к какой ошибке ведёт строгий?

Три правила обращения - какие, и почему сумму заменяют максимумом, а не суммой порядков?