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

Big O нотация, или Как оценить сложность алгоритма

Что такое алгоритм

Алгоритм - набор действий (инструкция), который компьютер может выполнить и который приведёт к нужному нам результату.

Как измерить сложность алгоритма

Просто измерять время выполнения двух алгоритмов не вариант, ибо один алгоритм может быстрее обработать 10 чисел, но в задаче с 1кк чисел он окажется медленнее, так как 2-й алгоритм может быть лучше оптимизирован именно под работу с большим кол-вом чисел.
Приходится придумывать вариант посложнее, который поможет оценить работу алгоритма с разными объёмами данных. Нужно описать связь между кол-вом операций и элементов. В математике это позволяет сделать подобная функция

$Y=f(X)$
значение $Y$ будет зависеть от значения $X$ по определённому правилу.

$Y=2\ast \ast X$
$Y$ будет всегда в $2$ раза больше $X$.

$Y=X\ast \ast 2+7\ast X-5$
Зависимость может быть любой - главное, что есть инструмент, с помощью которого можно описать такую зависимость.

Например, мы можем сравнить:
$Y=1000\ast X$
$Y=10000\ast X$

Если $Y$ - это зарплата, а $X$ - кол-во отработанных дней, мы и без калькулятора можно сделать выбор между этими двумя предложениями.
В нашем случае $Y$ - кол-во действий, которые алгоритм должен совершить, а $X$ - кол-во элементов, которые он должен обработать.

Если возьмём простую зависимость:
$Y=2\ast X$
то по такому описанию поймём, что алгоритм на каждый элемент выполняет по 2 действия. А значит, если нам надо будет обработать 100 элементов, алгоритм сделает это за 200 действий: $(Y=2\ast 100)=>(Y=200)$

$X$, $Y$ и $f(X)$ чаще используются в школьных задачах. Когда речь заходит об оценке сложности алгоритмов, принято использовать следующие обозначения:

$n$ - кол-во элементов;
$O(n)$ - функция от кол-ва элементов (по сути, это и есть $Y$ или $f(X)$ ).

Буквы другие, но суть та же - они сразу позволяют понять, что речь идёт о задаче оценки сложности алгоритмов.

---

Типичные примеры O-нотации (сложности алгоритмов)

Никаких сложных точных уравнений писать не нужно. Есть несколько общих вариантов зависимости, которые позволяют примерно оценить скорость работы алгоритма. По сути, не столько важно конкретное кол-во действий алгоритма, сколько важен порядок роста.
То есть мы отвечаем на вопросы вида: «Если алгоритм обработает 10 элементов за X действий, во сколько раз больше действий ему понадобится на 1 000 элементов?».

Ниже по порядку возрастания сложности все варианты:

• $O(1)$ - в этом случае у нас нет числа n, как нет и зависимости от кол-ва элементов. Такая оценка может быть, например, у алгоритмов, которые выполняют действие над одним элементом.
  Допустим, извлекают одну букву из строки. В строке может быть млрд букв, а может быть 10, но первую букву можно извлечь за одно действие.

• $O(logn)$ - $log$ может пугать, но достаточно просто запомнить, что эта оценка быстрее линейной зависимости. Если при линейной зависимости на 128 элементов мы потратим 128 действий, то при $O(logn)$:
  $log128=7$ - нам понадобится всего 7 действий.
  Кол-во действий будет расти с кол-вом элементов, но происходить это будет гораздо медленнее.

• $O(n)$ - линейная оценка, самая простая (но не самая эффективная, как мы видели ранее).
  Сколько элементов - столько и действий.

• $O(n\ast logn)$ - пожалуй, самая длинная из вариантов, она говорит о том, что алгоритм работает медленнее, чем при линейной оценке. Можем пересчитать пример со 128 элементами:
  $n\ast log(n)=128\ast 7=896$
  Получается значительная разница (и чем больше элементов - тем она будет существеннее).

• $O(n^2)$ - квадратичная зависимость, она ещё более медленная, чем предыдущая. Если там мы умножали $128\ast 7$, здесь нам пришлось бы умножать $128$ на $128$
  $128^2=128\ast 128=16384$

• $O(n!)$ - самая медленная оценка из базовых - факториал от числа элементов, который надо обработать. Для обработки 128 элементов пришлось бы считать следующую цепочку:
  $1\ast 2\ast 3\ast \dots \ast 127\ast 128$ ~ $3,85\ast 10^{215}$ - это число намного больше предыдущего большого числа.

Наглядно

Допустим, задача - разделить лист бумаги на 16/256/1024 прямоугольников.

Пусть компьютер выполняет 10 операций в секунду. Если мы выберем для решения задачи алгоритм со сложностью $O(logn)$, то для получения 16 прямоугольников нам понадобится всего 4 операции, и они выполнятся за 0,4 с.

---

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

python