Сложность алгоритмов

Одну и ту же задачу можно решить десятком разных способов. Как понять, какой из них лучше?

Можно измерить чистое время выполнения в секундах, но это ненадежно — зависит от аппаратной конфигурации и объема исходных данных. Поэтому придумали мерить сложность алгоритма в терминах количества операций.

Считать точное количество операций слишком хлопотно. Поэтому его описывают как зависимость от числа N — количества исходных данных, на которых работает алгоритм.

Такую оценку называют «Big-O» или «асимптотическим анализом» (потому что она работает для больших значений N).

Вот распространенные оценки алгоритмов от более быстрых (мало операций) к более медленным (много операций):

Константная сложность O(1)

Время выполнения алгоритма не зависит от объема исходных данных. Идеальный алгоритм!

Например, выбрать элемент из списка по индексу:

lst = [random.random() for _ in range(n)]
idx = random.randint(0, n-1)
# O(1)
lst[idx]

Логарифмическая O(log n)

При увеличении n время выполнения алгоритма растет такими же темпами, как log(n). Логарифм растет медленно (log 1000000 ≈ 20), так что даже при больших n логарифмические алгоритмы работают достаточно быстро.

Например, найти элемент в отсортированном списке:

el = random.random()
sorted_lst = sorted(lst)
# O(log n)
bisect.bisect(sorted_lst, el)

Линейная O(n)

Время выполнения алгоритма растет такими же темпами, как n. Как правило, такие алгоритмы перебирают все исходные данные.

Например, найти элемент в неотсортированном списке:

el = random.random()
# O(n)
idx = lst.index(el)

Линейно-логарифмическая O(n log n)

Время выполнения алгоритма растет такими же темпами, как n × log(n). Алгоритм получается медленнее, чем O(n), но не слишком (логарифм n намного меньше n, помните?).

Например, отсортировать список:

# O(n log n)
sorted(lst)

Продолжение следует ツ Если что непонятно — спрашивайте в комментариях.

Сложность алгоритмов: полиномиальные

Продолжаем рассматривать оценки скорости алгоритмов, которые часто встречаются на практике. С быстрыми (константные, логарифмические) и «условно-быстрыми» (линейные, линейно-логарифмические) мы разобрались. Продолжим «условно-медленными» — полиномиальными.

Квадратичная сложность O(n²)

Время выполнения растет как n². Обычно это значит, что алгоритм перебирает все элементы, и на каждом шаге перебирает их еще раз. На больших n квадратичные алгоритмы работают ощутимо медленно.

Например, сравнить два списка по принципу «каждый элемент с каждым»:

# O(n²)
for a in lst1:
  for b in lst2:
    print(a > b)

Полиномиальная O(nᵏ)

Время выполнения растет как n в некоторой фиксированной степени k: n³, n⁴, n⁵.

С одной стороны, по сравнению с O(log n) это медленно. С другой, когда действительно сложную задачу можно решить за полиномиальное время — это успех.

Если слышали о проблеме «P vs NP», то P — как раз полиномиальные (= быстрые) алгоритмы, а NP — суперполиномиальные (= медленные). Так что для некоторых задач O(nᵏ) очень даже быстро ツ

Строго говоря, линейные (k=1) и квадратичные (k=2) алгоритмы — частные случаи полиномиальных.

Пример полиномиального алгоритма — наивное умножение двух матриц. Выполняется за O(n³):

# A размера n×m
# B размера m×p
for i in range(0, n):
  for j in range(0, p):
    sum_ = 0
    for k in range(0, m):
      sum_ += A[i][k] * B[k][j]
    C[i][j] = sum_

Продолжение следует ツ Если что непонятно — спрашивайте в комментариях.

Сложность алгоритмов: суперполиномиальные

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

С быстрыми (константные, логарифмические), «условно-быстрыми» (линейные, линейно-логарифмические) и «условно-медленными» (полиномиальными) мы разобрались. Остались только улиточки — суперполиномиальные.

Экспоненциальная сложность O(2ⁿ)

Время выполнения растет как 2 в степени n. Это жутко медленные алгоритмы, при больших n они не выполнятся за вменяемое время даже на суперкомпьютерах.

Если у алгоритма экспоненциальная сложность — обычно использовать на реальных задачах его нельзя. Приходится изобретать пусть не самое оптимальное, зато быстрое решение.

Типичная задача с экспоненциальным временем решения — задача о рюкзаке:

Вор пробрался на склад, где хранится N ценных штуковин. У каждого предмета своя стоимость и вес. В рюкзаке можно унести барахла не больше X кг общего веса. Какой набор штуковин выбрать вору, чтобы унести добра на максимальную сумму?

Чтобы выбрать оптимальный набор, придется сравнить все возможные комбинации предметов — их как раз 2ⁿ (все подмножества множества из n элементов).

На практике можно решить, например, «жадным» алгоритмом, который сортирует предметы по удельной ценности (стоимость / вес), и набивает рюкзак по убыванию этой ценности, пока не закончится место. Сложность становится всего-то O(n logn) — хотя решение не оптимальное, конечно.

Или если веса целочисленные, задача о рюкзаке и вовсе решается методом динамического программирования за O(nX).

Факториальная O(n!)

Время выполнения растет как факториал от n (n! = n × (n-1) × (n-2) × ... × 1). Это жесть! Если алгоритм факториальной сложности — вы не сможете использовать его даже на наборе из 20 элементов.

Типичная задача с факториальным временем решения — задача коммивояжера:

Рьяному менеджеру по продажам нужно объехать N городов в разных точках страны. Как найти самый короткий маршрут, чтобы заехать в каждый город хотя бы раз и в итоге вернуться домой?

Выбрать первый город можно n способами, второй n-1, третий n-2, и так далее — так и получается n! маршрутов, среди которых приходится искать оптимальный.

На практике можно решать методом динамического программирования, который дает экспоненциальную сложность O(2ⁿn²). Тоже не вариант для больших n, но значительно быстрее факториального алгоритма.

Или забыть об оптимальном решении и считать жадным алгоритмом, который всегда выбирает ближайший город (O(n²)).

Окончание следует ツ Если что непонятно — спрашивайте в комментариях.

Сложность алгоритмов: итоги

Вот какие алгоритмы мы рассмотрели:

— Константные O(1)
— Логарифмические O(log n)
— Линейные O(n)
— Линейно-логарифмические O(n log n)
— Квадратичные O(n²)
— Полиномиальные O(nᵏ)
— Экспоненциальные O(2ⁿ)
— Факториальные O(n!)

O(1) — всегда лучший вариант, а O(log n) — почти всегда.

С полиномиальными сложнее — тут все зависит от задачи. Где-то стыдно выбирать O(n), а где-то и O(n²) будет большим успехом.

O(2ⁿ) и O(n!) не работают на больших n, поэтому на практике вместо них часто используют неоптимальные, но быстрые алгоритмы.

А еще с помощью «big-O» можно измерять потребление памяти алгоритмом. Там тоже много интересного.

Константного времени вашим алгоритмам! Ну или логарифмического ツ

Кстати! Если разбор алгоритмов показался вам суховатым или занудным, у меня есть короткое объяснение на котиках и с картинками 🐈
https://antonz.ru/big-o/

Если вы написали отличную статью, о которой никто не знает

В русскоязычном айти есть несколько «селебрити», которых все читают и обсуждают. И намного больше малоизвестных ребят, которые пишут классные статьи. У селебрити и так все отлично, а вот остальным я бы хотел помочь найти свою аудиторию.

Поэтому провожу эксперимент! Готов опубликовать ссылку на вашу статью, если она мне понравится. Бесплатно. Знаменитостью это вас не сделает, но статью точно увидит больше людей.

Все условия