«O» большое

Взял алгоритм в интернете, а он тормозит, хотя на тестовых данных все ок? Время разобраться почему!

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

Всем остальным и самому себе постараюсь объяснить попроще.

Время выполнения разных алгоритмов растет с разной скоростью.

Попробуем разобрать это на примерах простого и бинарного поисков по телефонному справочнику. Простой поиск — это когда идешь по-порядку по списку и находишь нужную фамилию. Бинарный поиск — это когда сперва открываешь справочник на середине, видишь что страница начинается с фамилии Петров, а ищем мы Лисина, значит нам нужно искать в первой половине книги. Делим эту половину еще пополам и повторяем операцию. И получается что в первом случае максимальное число операций по поиску равно количеству телефонных номеров, а во втором равно логарифму от количества элементов по основанию 2. Логарифм — операция, обратная возведению в степень. Записывается это как O(n) для простого и О(log2n) для бинарного поисков.

Допустим, что одна операция у нас занимает 1 мс.

Как видим результат на лицо, в зависимости от алгоритма скорость выполнения растет не линейно. И когда на небольшом количестве тестовых данных алгоритм может успешно отрабатывать, в боевом режиме можно успеть состарится. Поэтому при проектировании вспоминай про «О»-большое и учитывай как возрастет количество операций алгоритма с увеличением количества элементов.