Что такое О-большое (Big O) и зачем оценивать сложность алгоритма?

Точное время работы зависит от компьютера, языка и компилятора, поэтому алгоритмы сравнивают по тому, как растёт число операций при росте размера входа n. Запись O(f(n)) означает: начиная с некоторого n, затраты растут не быстрее, чем f(n), умноженная на константу.

При оценке:

• константы отбрасывают — O(2n) и O(n) один класс;
• младшие слагаемые отбрасывают — O(n² + n) это O(n²);
• разные входы обозначают разными буквами — обход двух массивов O(n + m), вложенный цикл по ним O(n·m).

Классы на примерах:

• O(1) — доступ к элементу массива по индексу, поиск в хеш-таблице в среднем;
• O(log n) — бинарный поиск: каждый шаг делит задачу пополам;
• O(n) — один проход по массиву;
• O(n log n) — хорошие сортировки сравнением;
• O(n²) — вложенный цикл по тем же данным, сортировка пузырьком;
• O(2ⁿ) — перебор всех подмножеств.

Разница огромная: при n = 1 000 000 алгоритм O(n log n) делает около 20 миллионов операций, а O(n²) — триллион.

Рядом с O используют Ω (оценка снизу) и Θ (точная оценка), но на собеседованиях чаще всего говорят «O» в смысле «как растёт в худшем случае».

def has_duplicates_slow(a):      # O(n²): сравниваем каждую пару
    return any(a[i] == a[j] for i in range(len(a)) for j in range(i + 1, len(a)))

def has_duplicates_fast(a):      # O(n): множество с проверкой за O(1) в среднем
    return len(set(a)) != len(a)