Оценка сложности алгоритма

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 с.

[[Алгоритмы, связанные со строками]]