- Подойти к холодильнику
- Достать из холодильника необходимые продукты
- Нарезать хлеб
- Намазать на него масло
- Положить сверху колбасу и сыр
Чтобы сделать бутерброд, вы выполняете некий набор действий. По сути, этот набор действий является алгоритмом приготовления бутерброда.
Алгоритм - набор инструкций для выполнения некоторой задачи. Как в реальной жизни, так и в программировании, люди на протяжении долгих лет выводили различные алгоритмы для эффективного решения тех или иных задач. Поэтому они являются фундаментальной основой программирования, которую нужно понимать и уметь применять на практике.
Для решения одной и той же задачи существуют различные алгоритмы. Каждый из них имеет свои плюсы и минусы, а также скорость выполнения. Понимая их различия и умея оценивать эффективность, вам будет проще выбирать алгоритмы для решения ваших задач.
Алгоритмы поиска
Операция поиска, пожалуй, одна из самых частых операций на сайтах и в различных приложениях. Поисковая строка гугл, адресная строка в браузере, поиск по имени в телефонной книге - поиск встречается абсолютно везде. Даже когда мы просто авторизируемся на сайте, введя логин и пароль, происходит поиск нашего аккаунта в базе данных.Поэтому, знакомство с алгоритмами мы начнем с алгоритмов поиска. Дальше мы рассмотрим простой и бинарный поиск, разберем их различия, плюсы и минусы.
Предположим, вы ищете фамилию человека в телефонной книге (если вы еще помните о их существовании). Она начинается с буквы «М». Конечно, можно начать с самого начала и перелистывать страницы, пока вы не доберетесь до буквы «М». Но скорее всего для ускорения поиска лучше раскрыть книгу на середине: ведь буква «М» должна находиться где то ближе к середине телефонной книги.
Или предположим, что вы ищете слово в словаре, и оно начинается с буквы «О». И снова будет быстрее начать с середины.
Перед нами типичные примеры задачи поиска, и для их решения идеально подойдет бинарный поиск.
Бинарный поиск - алгоритм поиска, который на входе получает отсортированный список элементов (дальше мы разберем, почему он должен быть отсортирован). Если элемент, который вы ищете, присутствует в списке, то бинарный поиск возвращает ту позицию, в которой он был найден. В противном случае он возвращает nil.
Давайте разберем сразу пример того, как работает бинарный поиск. Сыграем в простую игру: я загадал число от 1 до 100.
Вы должны отгадать мое число, использовав как можно меньше попыток. При каждой попытке я буду давать один из трех ответов: «мало», «много» или «угадал».
Предположим, вы начинаете перебирать все варианты подряд: 1, 2, 3, 4, ... Вот как это будет выглядеть:
- Вы: 1
- Я: мало
- Вы: 2
- Я: мало
- Вы: 3
- Я: мало
- ...
- Вы: 12
- Я: мало
- Вы: та ну тебя!!
Сами понимаете, такой подход к этой игре достаточно плохой и неэффективен. Это пример простого поиска. При каждой догадке, вы исключаете из вариантов только одно значение. Если я загадал 100, вам понадобится 100 попыток чтобы угадать число.
Существует другой, более эффективный способ играть в эту игру.
Давайте начнем с середины списка.
- Вы: 50
- Я: мало
К сожалению, вы не угадали. Но, совершив лишь один ход в игре, вы отсеяли 50 возможных вариантов!
- Вы: Окей, 75
- Я: мало
- Вы: 88
- Я: много
- Вы: 81.
- Я: Угадал!
Надеюсь, логику вы уже уловили. С бинарным поиском вы каждый раз загадываете число в середине диапазона и исключаете половину оставшихся чисел.
Только что вы узнали свой первый алгоритм!
Играя в эту игру, при простом поиске может понадобиться до 100 шагов в самом негативном сценарии. Как вы думаете, какое максимальное количество шагов при бинарном поиске?
Если перевести эти алгоритмы в язык математики, то, в самом плохом случае, простой поиск выполняется за N шагов, а бинарный за log2(N).
Примечание
Бинарный поиск работает только в том случае, если список отсортирован. Например, имена в телефонной книге хранятся в алфавитном порядке, и вы можете воспользоваться бинарным поиском. А что произойдет, если имена не будут отсортированы?
О-нотация или скорость выполнения алгоритма
Специальная нотация “О-большое” описывает скорость работы алгоритма. Зачем вам это нужно?Давайте вернемся к нашей игре. Если вам нужно отгадать число от 0 до 100, при простом поиске вы сделаете 100 попыток перед тем как угадать (в самом плохом сценарии) загаданное число. При бинарном же поиске у вас уйдет максимум 7 попыток (log2(100) ~ 7).
Допустим, мы написали программу, которая вместо нас угадывает числа. Для того, чтобы сделать одну догадку, у компьютера уходит 1 мс. При простом поиске алгоритм займет 100 мс, а при бинарном 7 мс.
На этом примере мы поняли, что бинарный поиск в 14 раз быстрее быстрого поиска.
А если мы увеличим диапазон? Теперь нужно угадать число от 0 до 1 000 000 000.
При бинарном поиске (log2(1 000 000 000) ~ 32) у нас уйдет примерно 32мс в самом плохом сценарии. Что ж, выполнив несложные математические действия, мы можем понять что быстрый поиск справиться с этой задачей за ~450 мс, в 14 раз дольше. Но так ли это?
Если вы подумали что это правильный вариант то вы ошибаетесь, очень глубоко ошибаетесь.
Дело в том, что время выполнения алгоритмов растет с разной скоростью.
При диапазоне чисел от 0 до 1 000 000 000 бинарному поиску понадобиться максимум 32 попытки угадать. Но при простом поиске, в самом плохом сценарии, понадобиться 1 миллиард попыток, или почти 11 дней!
Исходя из этого, мы можем понять, что с увеличением количества элементов бинарный поиск занимает чуть больше времени. А простой поиск займет гораздо больше времени. Таким образом , с увеличением списка бинарный список внезапно начинает работать гораздо быстрее простого.
Вот почему недостаточно знать, сколько времени должен работать алгоритм - необходимо знать, как возрастает время выполнения с ростом размера списка. Здесь-то вам и пригодится “О-большое”.
“О-большое” описывает, насколько быстро работает алгоритм. Предположим, имеется список размера N. Простой поиск должен проверить каждый элемент, поэтому ему придется выполнить N операций. Бремя выполнения “О-большое” имеет вид О(N).
Постойте, но где же секунды? А их здесь нет. “О-большое” не сообщает скорость в секундах, а позволяет сравнить количество операций. Оно указывает, насколько быстро возрастает время выполнения алгоритма.
А теперь другой пример. Для проверки списка размером N бинарному поиску потребуется log2N операций. Как будет выглядеть «О-большое»?
O(log2N) .
“O-большое” сообщает, какое количество операций необходимо выполнить алгоритму (в самом негативном сценарии).