Оценка сложности алгоритма
Big О нотация, или Как оценить сложность алгоритма
Что такое алгоритм
Алгоритм - набор действий (инструкция), который компьютер может выполнить и который приведёт к нужному нам результату.
Как измерить сложность алгоритма
Просто измерять время выполнения двух алгоритмов не вариант, ибо один алгоритм может быстрее обработать 10 чисел, но в задаче с 1кк чисел он окажется медленнее, так как 2-й алгоритм может быть лучше оптимизирован именно под работу с большим кол-вом чисел.
Приходится придумывать вариант посложнее, который поможет оценить работу алгоритма с разными объёмами данных. Нужно описать связь между кол-вом операций и элементов. В математике это позволяет сделать подобная функция
$Y = f(X)$
значение $Y$ будет зависеть от значения $X$ по определённому правилу.
$Y = 2 ** X$
$Y$ будет всегда в $2$ раза больше $X$.
$Y = X ** 2 + 7 * X – 5$
Зависимость может быть любой - главное, что есть инструмент, с помощью которого можно описать такую зависимость.
Например, мы можем сравнить:
$Y = 1000 * X$
$Y = 10000 * X$
Если $Y$ - это зарплата, а $X$ - кол-во отработанных дней, мы и без калькулятора можно сделать выбор между этими двумя предложениями.
В нашем случае $Y$ - кол-во действий, которые алгоритм должен совершить, а $X$ - кол-во элементов, которые он должен обработать.
Если возьмём простую зависимость:
$Y = 2 * X$
то по такому описанию поймём, что алгоритм на каждый элемент выполняет по 2 действия. А значит, если нам надо будет обработать 100 элементов, алгоритм сделает это за 200 действий: $(Y = 2 * 100) ⇒ (Y=200)$
$X$, $Y$ и $f(X)$ чаще используются в школьных задачах. Когда речь заходит об оценке сложности алгоритмов, принято использовать следующие обозначения:
$n$ - кол-во элементов;
$O(n)$ - функция от кол-ва элементов (по сути, это и есть $Y$ или $f(X)$ ).
Буквы другие, но суть та же - они сразу позволяют понять, что речь идёт о задаче оценки сложности алгоритмов.
Типичные примеры O-нотации (сложности алгоритмов)
Никаких сложных точных уравнений писать не нужно. Есть несколько общих вариантов зависимости, которые позволяют примерно оценить скорость работы алгоритма. По сути, не столько важно конкретное кол-во действий алгоритма, сколько важен порядок роста.
То есть мы отвечаем на вопросы вида: «Если алгоритм обработает 10 элементов за X действий, во сколько раз больше действий ему понадобится на 1 000 элементов?».
Ниже по порядку возрастания сложности все варианты:
-
$О(1)$ - в этом случае у нас нет числа n, как нет и зависимости от кол-ва элементов. Такая оценка может быть, например, у алгоритмов, которые выполняют действие над одним элементом.
Допустим, извлекают одну букву из строки. В строке может быть млрд букв, а может быть 10, но первую букву можно извлечь за одно действие. -
$О(log n)$ - $log$ может пугать, но достаточно просто запомнить, что эта оценка быстрее линейной зависимости. Если при линейной зависимости на 128 элементов мы потратим 128 действий, то при $O(log n)$:
$log 128 = 7$ - нам понадобится всего 7 действий.
Кол-во действий будет расти с кол-вом элементов, но происходить это будет гораздо медленнее. -
$O(n)$ - линейная оценка, самая простая (но не самая эффективная, как мы видели ранее).
Сколько элементов - столько и действий. -
$О(n * log n)$ - пожалуй, самая длинная из вариантов, она говорит о том, что алгоритм работает медленнее, чем при линейной оценке. Можем пересчитать пример со 128 элементами:
$n * log (n) = 128 * 7 = 896$
Получается значительная разница (и чем больше элементов - тем она будет существеннее). -
$О(n^2)$ - квадратичная зависимость, она ещё более медленная, чем предыдущая. Если там мы умножали $128 * 7$, здесь нам пришлось бы умножать $128$ на $128$
$128^2 = 128 * 128 = 16 384$ -
$О(n!)$ - самая медленная оценка из базовых - факториал от числа элементов, который надо обработать. Для обработки 128 элементов пришлось бы считать следующую цепочку:
$1 * 2 * 3 * … * 127 * 128$ ~ $3,85 * 10^{215}$ - это число намного больше предыдущего большого числа.
Наглядно
Допустим, задача - разделить лист бумаги на 16/256/1024 прямоугольников.
Пусть компьютер выполняет 10 операций в секунду. Если мы выберем для решения задачи алгоритм со сложностью $O(log n)$, то для получения 16 прямоугольников нам понадобится всего 4 операции, и они выполнятся за 0,4 с.
