Компьютерные алгоритмы – Binary Search и Big O нотация

Как ускорить поиск с 301 067 операций до 18.

В жизни каждого разработчика наступает момент, когда ему приходится знакомиться с алгоритмами. У кого-то, кто учится на Computer Science, он наступает раньше, у кого-то, кто учится сам — позже.

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

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

На мой взгляд, каждая сторона права по своему. Front-end разработчикам алгоритмы действительно бывают не нужны, если работа не связана с бизнес-логикой. Собирать фронты на Vue/React/Angular, делать их адаптивными, красивыми и анимированными - тут подобные знания не пригодятся. А всю тяжелую работу делает бекенд.

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

Давайте для примере разберем один базовый алгоритмов, который известен как Binary Search.

Есть массив сортированных чисел.

Я загадываю число, которое есть в массиве. А вам надо его отгадать.

Отгадать надо с наименьшего количества попыток. После каждой попытки я говорю — была ли попытка «слишком мало» или «слишком много». Как «тепло»/«холодно».

Самое быстрое и лежащее на поверхности решение данной проблемы с точки зрения кода — «простой поиск» — начинаем искать с наименьшего числа, и идем до конца, пока не найдем нужное.

Например, я загадываю 416.

Если поставить внутри цикла принт, то можно посчитать, сколько будет операций поиска. Я загадал предпоследнее, поэтому их будет количество чисел минус один.

Есть другой способ — Binary Search.

Работает он так — искать начинаем с середины списка.

Представим, что список у нас от 0 до 1000, и загадано число 600.

Число на позиции 500 - слишком много, или слишком мало ?

— Слишком мало

Ага, таким образом все, что меньше, нас не интересует. Ищем в оставшейся половине.

— А на позиции 750 ?

— Слишком много.

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

Таким образом не надо просеивать последовательно весь список.

• Объявляем минимальную границу поиска - первый индекс в списке.
• Объявляем максимальную границу поиска - последний индекс в списке.
• Идем циклом, пока нижняя граница не станет равной максимальной или не будет найден нужен индекс.Если ничего не нашли - возвращаем пустоту.
• В цикле начинаем с того, что ищем индекс середины между текущей минимальной и максимальной границами. Найдя его, достаем из массива по этому индексу число - кандидат.
• Если кандидат равен загаданному числу - все супер, мы нашли.
• Если кандидат больше загаданного числа, то меняем верхнюю границу поисков – уменьшаем текущую середину на 1.
• Если кандидат меньше загаданного числа, то меняем верхнюю границу поисков – увеличиваем текущую середину на 1.

Если после строки let candidate = numbers[middle] добавить принт, то можно проследить, как работает алгоритм.

Поиск нашел нужное число за 4 попытки.

Представим, что мы ищем индекс записи в списке адресов, в котором 400 000 записей.

Сколько операций поиска надо сделать, когда загадано число 301 067, используя простой поиск ?

Правильно, 301 067.

А используя бинарный поиск - 18.

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

Существует так называемая Big O нотация. Она описывает, насколько алгоритм быстр в использовании. Если у нас есть список длинной n, то обычный поиск будет искать в нем индекс со скоростью O(n) — чем больше элементов в списке, чем больше величина n. А бинарный – O(log n). Берется всегда самый худший кейс, на нашем примере – число загаданное в самом конце.

На всякий случай напомню, что такое логарифм

Логарифм — это степень, в которую надо возвести число после log, чтобы получить число перед знаком равно.

log(2)8 = 3

log(2)4 = 2

log(2)16 = 4

Кроме O(n) и O(log n) чаще всего встречаются следующие сложности

• O(1) - константа. Сложность всегда одинаковая, для любого объема данных. Например, сравнение двух чисел.
• O(n!) - факториал. Пример, Задача коммивояжёра.
• O(n в квадрате) - квадратичная сложность. Пример - сортировка пузырьком.

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

На этом у меня сегодня все.

Пока!

PS: Не обижайте алгоритмы, иногда они бывают полезны.