Как в учебнике
Пусть $n\in\mathbb N$ стремится к бесконечности, а начиная с некоторого номера $f(n)\ge0$ и $g(n)>0$. Запись $f\in O(g)$ означает, что существуют постоянные $C>0$ и $n_0$ с $f(n)\le Cg(n)$ для всех $n\ge n_0$. Это верхняя оценка роста.
Множитель $C$ и порог $n_0$ выбираются один раз и не зависят от $n$. Конечное число начальных исключений разрешено; постоянное изменение множителя вместе с входом — нет. Для $f(n)=3n+7$ подходят $C=10$ и $n_0=1$, поскольку $3n+7\le10n$ при $n\ge1$.
Класс $O(g)$ содержит функции, рост которых ограничен постоянным кратным $g$. Привычное $f(n)=O(g(n))$ — сокращение принадлежности классу, а не симметричное равенство двух чисел. Верхняя оценка не обязана быть точной: $3n+7\in O(n^2)$ также верно.
Для алгоритма сначала указывают размер входа, модель операций и рассматриваемый случай. Оценку можно давать времени в худшем, лучшем или ином выбранном случае; буква O сама не означает «худший случай». Дополнительную память оценивают отдельно от времени.
Для выбранных неотрицательных функций с $g(n)>0$ условие равносильно ограниченности отношения $f(n)/g(n)$ сверху на некотором хвосте. Чтобы опровергнуть предложенную оценку, нужно показать, что никакой фиксированный множитель не удержит это отношение. Например, $n^2$ не принадлежит $O(n)$: из $n^2\le Cn$ следовало бы $n\le C$, что нарушается при достаточно большом $n$.
Определения и обозначения: Mathematics for Computer Science.
Связанные понятия: Θ-большое: точный порядок роста, o-малое: пренебрежимо меньший рост.
На пальцах
Верхняя оценка похожа на потолок, под которым после некоторого порога помещается весь график затрат. Потолок разрешено поднять постоянным множителем, но для каждого нового входа его уже нельзя надстраивать. Линейные затраты помещаются и под квадратичным потолком, поэтому верная оценка бывает избыточно высокой. Обещание «аренда не дороже бюджета страны» может быть честным, но мало помогает при выборе квартиры: O задаёт границу роста, а не точное время работы.
Пример
Учебная функция $f(n)=3n+7$ считает условные операции. Один и тот же потолок $10n$ проверяется на растущих входах.
O-большое: верхняя оценка роста
Вход 1
При n = 1 потолок достигается точно.
Шаг 1 из 4: Вход 1
Все шаги текстом
Вход 1
При n = 1 потолок достигается точно.
- n; f(n); 10n
- 110включён10текущий
Вход 2
Множитель остаётся 10; функция уже ниже потолка.
- n; f(n); 10n
- 213включён20текущий
Вход 10
На большем входе тот же постоянный множитель работает.
- n; f(n); 10n
- 1037включён100текущий
Все дальнейшие входы
Из 7 ≤ 7n при n ≥ 1 следует требуемая оценка для всех таких n.
- C; n₀
- 10включён1включён
Первые три состояния только проверяют числа: 10, 13 и 37 действительно не превышают 10, 20 и 100. Последнее состояние объясняет, почему совпадение продолжится. При $n\ge1$ добавка 7 ограничена величиной $7n$, после чего обе линейные части складываются в $10n$. Здесь множитель 10 выбран с запасом; искать наилучший множитель для принадлежности классу не требуется.
Численная таблица проверяет примеры; последнее неравенство обосновывает оценку для всего хвоста.