Оценка асимптотической сложности алгоритмов

Асимптотическая сложность

Сложность — функция размера входа n: число операций или объем дополнительной памяти при росте n. Асимптотика игнорирует постоянные множители и младшие слагаемые:

3n² + 20n + 100 ∈ Θ(n²)

O, Ω и Θ

• f(n) ∈ O(g(n)) — асимптотическая верхняя граница.
• f(n) ∈ Ω(g(n)) — нижняя граница.
• f(n) ∈ Θ(g(n)) — одновременно верхняя и нижняя, точный порядок роста.

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

Как определить размер входа

• массив — число элементов;
• матрица — отдельно строки r и столбцы c, а не автоматически n;
• граф — вершины V и ребра E;
• число — иногда значение N, иногда количество его бит log N.

Случаи

• worst case дает гарантированную верхнюю оценку;
• average case требует модели распределения входов;
• best case показывает удачный вход, но редко является гарантией;
• amortized распределяет редкую дорогую операцию по последовательности, например расширение ArrayList.

Порядки роста

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Примеры:

for (int i = 1; i < n; i *= 2) { } // Θ(log n)
 
for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++) { } // Θ(n²), сумма 0 + ... + n-1

Последовательные этапы складываются, вложенные независимые циклы умножаются. Но O(n + m) нельзя превращать в O(n), если размеры независимы.

Пространство

Считают дополнительную память помимо входа. Рекурсивная функция может не создавать массивов, но использовать O(depth) stack frames.

На собеседовании

• O означает худший случай? Нет, это вид верхней границы; случай задается отдельно.
• Почему бинарный поиск log n? Пространство поиска каждый шаг делится пополам.
• Какова сумма треугольного цикла? n(n-1)/2, то есть Θ(n²).
• Что такое amortized O(1)? Средняя стоимость операции по длинной последовательности, не вероятностный average case.
• Размер входа поиска делителей числа N? В битовой модели log N, поэтому оценку O(sqrt(N)) важно интерпретировать.