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

Давайте посмотрим, как программисты оценивают быстрые и медленные алгоритмы. Поскольку тема максимально занудная, разбираться будем на дурацких примерах с котиками.

Константное время, O(1)

Самый лучший вариант, скорость алгоритма не зависит от количества котиков.

🐾 Пример

Вы — счастливый обладатель N котиков. Каждый котик знает, как его зовут. Если позвать «Клёпа!», то прибежит только он, а остальным N-1 жопкам пофиг.

Константное время

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

На N котиках алгоритм отрабатывает за log(N) шагов. Это быстро! 1 000 000 котиков → всего 20 операций.

🐾 Пример

Мисочки у котиков расставлены по алфавиту. Когда у вас появляется новый котик, место для его мисочки находится за log(N) шагов.

Логарифмическое время

Линейное время, O(n)

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

🐾 Пример

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

Линейное время

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

На N котиках алгоритм отрабатывает за N × log(N) шагов. Это дольше, чем за линейное время, но ненамного (логарифм N сильно меньше N, помните?).

🐾 Пример

К приходу гостей вы решили рассадить котиков по размеру. Алгоритм quick sort справится с этим за N × log(N) шагов.

Линейно-логарифмическое время

На очереди у нас неторопливые полиномиальные котики и совсем улиточки — суперполиномиальные.

Квадратичное время O(n²)

На N котиках алгоритм отрабатывает за шагов. Ме-е-едленно.

🐾 Пример

Конкурент утверждает, что его N котиков более гладкие и довольные, чем ваши. Специальная комиссия попарно сравнит хвостатых и вынесет справедливый вердикт. Понадобится ~  сравнений.

Квадратичное время

Полиномиальное время, O(nᵏ)

На N котиках алгоритм отрабатывает за  шагов, N⁴ шагов, N⁵ шагов, или ещё дольше. Фу таким быть.

🐾 Пример

Фотосессия! Каждого из N котиков надо попарно отфоткать с другими, причем фотограф делает N снимков на каждую пару. N × N × N ≃  шагов.

Полиномиальное время

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

Экспоненциальное время, O(2ⁿ)

На N котиках алгоритм отрабатывает за 2ⁿ шагов. Это долго, вы вряд ли дождетесь.

🐾 Пример

Котики отправляются на выставку. Каждого взвесили и оценили в звездах. Но перевозка рассчитана максимум на X килограмм. Как выбрать самый звездный состав? Ответ потребует 2ⁿ шагов.

Экспоненциальное время

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

На N котиках алгоритм отработает за N × (N-1) × (N-2) ×… × 1 шагов. Это жесть! Всего 20 котиков уже дадут нам пару квинтиллионов операций.

🐾 Пример

Котики расселись по квартире. Вам хочется пожамкать каждого, но ходить лень. Какой кратчайший маршрут, чтобы обойти всех шерстяных жопок? Это ~ N! сравнений.

Факториальное время

Резюме

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

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

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

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

Всем котиков! И подписывайтесь на @nalgeon в твитере, чтобы не пропустить новые заметки 🚀