Big-O и формальное верхнее ограничение
Как объяснить сложность алгоритма и формальное определение O-большого через константы и размер входа?
Короткий ответ
Big-O описывает верхнюю асимптотическую границу: f(n)=O(g(n)), если после некоторого n0 существует константа C, такая что f(n)<=C*g(n).
Полный разбор
Сначала можно сказать интуитивно: сложность показывает, как растут время или память алгоритма при росте размера входа. Обычно оставляют доминирующий член и игнорируют константы, потому что нас интересует масштабирование.
Формально f(n)=O(g(n)), если существуют C>0 и n0, такие что для всех n>=n0 выполняется f(n)<=C*g(n). Поэтому 3n+10 это O(n), а n log n обычно не O(n), потому что отношение растет.
На интервью хорошо разобрать пример: один цикл - O(n), два вложенных цикла - O(n^2), сортировка - O(n log n), два независимых входа - O(n+m).
Теория
Asymptotic analysis сравнивает функции роста, а не точное время выполнения конкретной программы.
Типичные ошибки
- Складывать все шаги без выделения доминирующего члена.
- Забывать про разные размеры входа n и m.
- Называть Big-O точным временем работы.
Как отвечать на собеседовании
- Дай интуицию, а потом формальное C и n0.
- Всегда связывай сложность с размером входа.