Формальное определение «O», «Θ», «Ω» большого.

Пришло время дать более строгие определения понятий, связанных с оценкой алгоритмической сложности. Не пугайтесь формул, по сути они передают то, о чём шла речь в прошлом уроке.
На математическом языке фраза «сложность алгоритма — O(n)O(n)» означает, что с увеличением параметра nn (то есть количества данных на входе) время работы алгоритма будет возрастать не быстрее, чем некоторая константа kk, умноженная на nn. То есть, начиная с какого-то n0n_0 функция T(n)T(n) расположена ниже, чем график функции y=kny = kn для некоторого kk.
Нужно понимать, что для небольших значений nn это может быть совсем не так.
image
Важно, как алгоритм будет работать на больших объемах данных. Другими словами, как будет вести себя функция при очень больших значениях параметра nn. При оценке O-большого часто используется понятие асимптотической сложности. Так называется вычислительная сложность алгоритма при nn, стремящимся к бесконечности.
Более формально:
image
На самом деле O(g(n))O(g(n)) — это класс функций, ограниченный сверху функцией g(ng(n). Вернее было бы написать f(n)∈O(g(n))f(n) \in O(g(n)). Знак равенства используют скорее для удобства. Это не равенство в привычном смысле, а несимметричное отношение. Мы не можем прочитать это равенство в обратную сторону.
image
Обратите внимание, мы как будто отбросили слагаемые 5n5n и 11.
Чтобы разобраться, почему так можно делать, посмотрим на график:
image
Видно, что функции y=7×n2y = 7 \times n^2 и y=7×n2+5n+1y = 7 \times n^2 + 5n + 1 c увеличением nn ведут себя примерно одинаково.
То есть слагаемые 5n5n и 11 вносят несущественный вклад по сравнению с 7n27n^2, особенно при больших nn. Эти слагаемые имеют меньшую скорость роста, чем 7n27n^2. Формальное доказательство данного факта будет чуть позже в этом уроке. Поэтому их можно не принимать во внимание.
Также важно отметить, что мы не учитываем множитель 77 при n2n^2, когда пишем, что 7n2+5n+1=O(n2)7n^2 + 5n + 1 = O(n^2). Этот множитель часто называют коэффициентом амортизации. Сейчас разберёмся, почему его можно опустить.
Вы уже знаете, что при оценке вычислительной сложности не учитывают такие факторы как процессор, операционная система компьютера и язык программирования, на котором реализован алгоритм.
Допустим, процессор на одном компьютере в два раза быстрее, чем на втором. Алгоритм, реализованный на C++, может закончить работу в полтора раза быстрее, чем алгоритм, написанный на Python. Принимать это во внимание мы не хотим.
Поэтому константа игнорируется при определении O(n)O(n).
Если вы, к примеру, обрабатываете массив, проходясь последовательно по всем его элементам, то для определения O(n)O(n) неважно, будет ли на каждом шаге произведена одна, две или десять операций. Учитывают только переменные, зависящие от объёма входных данных.
Представьте отбор в команду волейболистов. В команде может быть произвольное количество игроков, но все они должны быть ростом не ниже пяти сантиметров по сравнению с самым высоким из них. Эту задачу можно решить за два прохода. Сначала определить рост самого высокого человека, затем — выбирать игроков, сравнивая рост каждого с найденным на первом шаге максимумом. Будет сделано два шага, но все равно сложность останется O(n)O(n).
image
Если нужно отобрать пять самых высоких игроков, можно отсортировать их по росту. Пятеро первых и будут самыми высокими. Воспользуемся алгоритмом «сортировка выбором»: на каждом шаге ii выбираем наименьший элемент в массиве и меняем его местами с элементом на позиции ii. Реализацию (код) алгоритма сейчас рассматривать не будем — сортировкам посвящён отдельный урок. А пока посмотрите, как он работает:
Сколько операций потребуется для алгоритма «сортировка выбором»? На каждой итерации ii, где ii принимает значение от 11 до nn, сравниваем элемент на ii-ой позиции (n−i−1)(n - i - 1) раз. Получим, что сложность будет O(n2)O(n^2).
Теперь представьте, что каждый раз при сравнении вы записываете данные, чтобы потом проверить свои действия. Операций потребуется в два раза больше, ведь вы ещё запоминаете результат каждой операции сравнения. Но два — это константа, а константы не влияют на асимптотику, то есть всё равно сложность алгоритма будет O(n2)O(n^2).
Теперь интуитивно понятно, почему при оценке мы опускаем некоторые слагаемые. Давайте покажем это строго:
image
Получаем, что функции y=7n2+5n+1y = 7n^2 + 5n + 1 и y=n2y = n^2 при больших nn отличаются на константу. То есть можно взять такую константу, что график функции y=7n2+5n+1y = 7n^2 + 5n + 1 начиная с какого-то n0n_0 будет лежать ниже графика функции y=n2y = n^2 умноженную на эту константу. По определению получаем, что 7n2+5n+1=O(n2)7n^2 + 5n + 1 = O(n^2).
Выражение 7n2+5n+1=O(n2)7n^2 + 5n + 1 = O(n^2) означает, что функция 7n2+5n+17n^2 + 5n + 1. ограничена сверху функцией y=n2y = n^2, умноженной на некоторую константу.
Корректно будет сказать, что, например:
image
Но при анализе сложности алгоритмов мы хотим найти наиболее точную оценку. То есть нужно определить функцию, ограничивающую нашу функцию сверху, но как можно более близкую к ней.
Выражение y=7×n2y = 7 \times n^2 и y=7×n2+5n+1=O(n2)y = 7 \times n^2 + 5n + 1 = O(n^2) говорит о следующем. Если при больших nn алгоритм работает примерно секунду, то при удвоении объёма данных время работы возрастет в четыре раза.
Помимо O(n)O(n) существуют другие оценки сложности алгоритмов: Θ(n)\Theta (n) (Θ\Theta произносится «тета») и Ω(n)\Omega(n) (Ω\Omega произносится «омега»).
image
На графиках показан смысл этих трёх показателей:
image
Однако на практике чаще всего используют O(n)O(n). Эту характеристику обычно проще посчитать, и она более полезна.
Подведём итог. Вы познакомились с O-символикой (так по-другому называют О - нотацию).
Плюсы метода:
  • Помогает определить зависимость времени работы алгоритма от объёма входных данных.
  • Позволяет сравнивать алгоритмы между собой.
  • Упрощает анализ сложности. Нам не нужно задумываться о том, сколько на самом деле занимает каждая операция.
  • Сложность алгоритма не зависит от машины, на которой запускается программа, языка программирования и других факторов, учитывать которые мы не хотим.
  • Даёт более простые оценки сложности: O(n3)O(n^3) вместо 5n3+2n2+45n^3 + 2n^2 + 4.
Но, как и у многих методов, у данного подхода есть недостатки.
При его использовании не учитываются константы и слагаемые, имеющие меньшую скорость роста.
На практике есть разница, будет алгоритм работать за n2n^2 или, к примеру, за 3n23n^2. Константы имеют значение. Будет ли ваша программа работать 10 или 100 секунд, будут ли в функции слагаемые, имеющие меньшую скорость роста и поэтому отброшенные при анализе, — все это играет роль. Если вы хотите писать эффективный код, следует обращать внимание не только на асимптотическую сложность.
Допустим, для решения задачи есть два алгоритма с одинаковой асимптотической сложностью O(n2)O(n^2). Но функция временной сложности первого имеет вид T(n)=3n2T(n) = 3n^2, а второго — 1000n2+100n1000n^2 + 100n, то стоит выбрать первый.
Есть определённые правила оценки эффективности алгоритмов с применением «O» большого. О них вы узнаете в следующем уроке.