Компьютерные алгоритмы – 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
Существует так называемая 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: Не обижайте алгоритмы, иногда они бывают полезны.