O: верхняя граница с точностью до множителя

Если можешь доказать f(n) = O(g(n)), назвав конкретные c и n₀, - листай до «Теперь сам».

Как думаешь, можно ли назвать это «порядка n²»

Точный счёт из прошлой главы дал T(n) = 3n² + 500n + 2000. В прошлой главе мы на глаз выбросили младшее и множитель и сказали «порядка n²». Но в формуле живьём стоят и 500n, и 2000 - на входе n = 4 слагаемое 500n даже больше 3n². По какому праву мы называем это n²? Нужен критерий, который превращает «на глаз» в проверяемое утверждение.

На что это похоже

O(g) - это потолок, под которым функция оказывается, когда разгонится. Представь ограничение скорости на трассе: пока въезжаешь, на разгоне ты можешь его превысить, но с какого-то момента и дальше держишься под ним. Множитель c - высота потолка (можно взять с запасом), порог n₀ - место, с которого правило начинает соблюдаться. Что творится до n₀, потолок не волнует.

Механизм: определение через c и n₀

f(n) = O(g(n)), если существуют положительное число c и порог n₀, такие что

f(n) ≤ c·g(n)   для всех n ≥ n₀

Здесь два разных знака вопроса, и каждый закрывает свою неопределённость. Множитель c глотает константу: неважно, что у f перед n² стоит 3, а у g - единица; достаточно взять c побольше, и c·g перекроет f. Порог n₀ глотает малые входы: на разгоне младшие слагаемые могут задирать f выше c·g, но нас интересует поведение на большом n, поэтому мелочь до n₀ разрешено не учитывать. Оба «с точностью до» из прошлой главы - множитель и «при большом n» - здесь стали частью определения.

Знак = в f(n) = O(g(n)) - вольность записи: O(g) это целый НАБОР функций, растущих не быстрее g, и правильнее читать «f принадлежит O(g)». Но пишут традиционно через равенство.

Правило

f(n) = O(g(n)) тогда и только тогда, когда найдутся c > 0 и n₀, при которых f(n) ≤ c·g(n) для всех n ≥ n₀. Доказать принадлежность - предъявить такую пару c, n₀. Опровергнуть - показать, что никакая пара не годится.

Разбор: докажем 3n² + 500n + 2000 = O(n²)

Нужно предъявить c и n₀. Возьмём c = 4 и потребуем 3n² + 500n + 2000 ≤ 4n². Перенесём: это то же самое, что 500n + 2000 ≤ n². Левая часть растёт линейно, правая квадратично, значит с какого-то n правая обгонит. Проверим n = 505: слева 500·505 + 2000 = 254 500, справа 505² = 255 025 - неравенство выполнено, и дальше разрыв только растёт. Значит при c = 4, n₀ = 505 условие держится - принадлежность доказана.

Пара не единственная. Взяв c = 3.01, порог n₀ придётся отодвинуть далеко; взяв c = 100, наоборот, неравенство выполнится почти сразу. Это и есть смысл «с точностью до множителя»: свобода в c позволяет игнорировать константы, а свобода в n₀ - разгон.

Разбор: O - это ПОТОЛОК, а не точное значение

n = O(n²) - истинное утверждение: линейная функция растёт не быстрее квадратичной, возьми c = 1, n₀ = 1, и n ≤ n² для всех n ≥ 1. Звучит странно - линию назвали O(n²), - но O и есть верхняя граница, а не обещание равенства. Поэтому «алгоритм работает за O(n²)» означает «не медленнее квадрата», и линейный алгоритм этому честно удовлетворяет. Если хочется сказать «ровно квадрат, не быстрее и не медленнее», нужна другая запись - Θ, о ней следующий урок.

Что ломается без этого

Две частые ошибки чтения O. Первая - принять O за точное равенство: увидев O(n²), решить, что алгоритм обязательно делает n² шагов, тогда как это лишь верхняя граница. Вторая - спутать O с худшим случаем: O описывает рост функции, а какую именно функцию берут (время худшего случая, лучшего, среднего) - отдельный вопрос из главы про случаи. Можно сказать «в лучшем случае O(n)» - это не противоречие, а просто верхняя граница для функции лучшего случая.

Зачем это в работе

O - это язык, на котором документация обещает скорость: «поиск в словаре - O(1)», «сортировка - O(n·log n)». За этими значками стоит ровно определение с c и n₀: гарантия не про конкретную машину (её съедает c) и не про крошечные входы (их съедает n₀), а про то, как время растёт с размером данных. Прочитав O(n²) у чужой функции, ты знаешь: на вдвое большем входе она может замедлиться вчетверо, и планируешь, исходя из этого.

Теперь сам

Докажи, что 5n + 100 = O(n), назвав c и n₀. И реши: верно ли, что n² = O(n)?