«O» большое - скорость алгоритма

Специальное соглашение «О-большое» описывает скорость работы алгоритма. Важно понимать, знать насколько быстро или медленно работают алгоритмы. Время выполнения алгоритма может расти с разной скоростью.  Например при поиске элементов. Допустим один шаг, одна итерация алгоритма выполняется 1мс. Значит при обработке 100 элементов время выполнения будет 100мс. Для бинарного поиска, чтобы найти нужный элемент потребуется всего ~7 итераций. Значит выполнение алгоритма займет всего 7мс. Разница очевидна. Теперь представим что поиск нужно осуществить по тысячам или миллионам элементов. И так, Log21000000 ≈ 20 (19,93..). Это впечатляет, 1 000 000 мс (~16 минут) против 20мс. Если же надо перебрать 1 миллиард элементов (1 000 000 000), то разница будет просто устрашающей, 11 дней против ~32мс.

То есть, знать и понимать скорость алгоритма критически важно.

n - количество операций

O(n) - линейное время (просто перебор, поиск)
O(log n) - логарифмическое время (пример выше, бинарный поиск)
O(n * log n) - например быстрая сортировка
O(n2) - медленная сортировка (сортировка выбором)
O(n!) - очень медленные алгоритмы

Задача о коммивояжере

Пример из книги "Грокаем алгоритмы", Анитья Бхарава

Известная задача из области теории вычислений, в которой
время выполнения растет с просто ужасающей скоростью, и некоторые
очень умные люди считают, что с этим ничего не поделать. Она называется задачей о коммивояжере.

Коммивояжер должен объехать 5 городов. Коммивояжер хочет побывать в каждом из 5 городов так, чтобы при этом проехать минимальное общее расстояние. Одно из возможных решений: нужно перебрать все возможные комбинации порядка объезда городов.

Все расстояния суммируются, после чего выбирается путь с кратчайшим
расстоянием. Для 5 городов можно создать 120 перестановок, поэтому реше­ние задачи для 5 городов потребует 120 операций. Для 6 городов количество операций увеличивается до 720 (существуют 720 возможных перестановок). А для 7 городов потребуется уже 5040 операций!

В общем случае для вычисления результата при n-элементах потребуется n! (n-факториал) операций. А значит, время выполнения составит О(n!) (такое время называется факториальным). При любом сколько-нибудь серьезном размере списка количество операций будет просто огромным. Скажем, если вы попытаетесь решить задачу для 100+ городов, сделать это вовремя не удастся — Солнце погаснет раньше.

Какой ужасный алгоритм! Значит, коммивояжер должен найти другое
решение, верно? Но у него ничего не получится. Это одна из знаменитых нерешенных задач в области теории вычислений. Для нее не существует известного быстрого алгоритма, и ученые считают, что найти более эффективный алгоритм для этой задачи в принципе невозможно.