Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - Адитья Бхаргава
Шрифт:
Интервал:
Закладка:
При простом поиске может потребоваться 240 000 попыток, если искомое слово находится на самой последней позиции в книге. С каждым шагом бинарного поиска количество слов сокращается вдвое, пока не останется только одно слово.
Итак, бинарный поиск потребует 18 шагов — заметная разница! В общем случае для списка из n элементов бинарный поиск выполняется за log2n шагов, тогда как простой поиск будет выполнен за n шагов.
Логарифмы
Возможно, вы уже забыли, что такое логарифм, но наверняка помните, что такое возведение в степень. log10100 по сути означает, сколько раз нужно перемножить 10, чтобы получить 100. Правильный ответ — 2: 10 × 10. Итак, log10 100 = 2. Логарифм по смыслу противоположен возведению в степень.
Логарифм — операция, обратная возведению в степень
Когда я в этой книге упоминаю «O-большое» (об этом чуть позднее), log всегда означает log2. Когда вы ищете элемент с применением простого поиска, в худшем случае вам придется проверить каждый элемент. Итак, для списка из 8 чисел понадобится не больше 8 проверок. Для бинарного поиска в худшем случае потребуется не более logn проверок. Для списка из 8 элементов log 8 == 3, потому что 23 == 8. Итак, для списка из 8 чисел вам придется проверить не более 3 чисел. Для списка из 1024 элементов log 1024 = 10, потому что 210 == 1024. Следовательно, для списка из 1024 чисел придется проверить не более 10 чисел.
примечание
Бинарный поиск работает только в том случае, если список отсортирован. Например, имена в телефонной книге хранятся в алфавитном порядке, и вы можете воспользоваться бинарным поиском. А что произойдет, если имена не будут отсортированы?
Посмотрим, как написать реализацию бинарного поиска на Python. В следующем примере кода используется массив. Если вы не знаете, как работают массивы, не беспокойтесь: эта тема рассматривается в следующей главе. Пока достаточно знать, что серию элементов можно сохранить в непрерывной последовательности ячеек, которая называется массивом. Нумерация ячеек начинается с 0: первая ячейка находится в позиции с номером 0, вторая — в позиции с номером 1 и т.д.
Функция binary_search получает отсортированный массив и значение. Если значение присутствует в массиве, то функция возвращает его позицию. При этом мы должны следить за тем, в какой части массива проводится поиск. Вначале это весь массив:
low = 0
high = len(list) - 1
Каждый раз алгоритм проверяет средний элемент:
mid = (low + high) / 2 Если значение (low+high) нечетно, то Python автоматически округляет значение mid в меньшую сторону
guess = list[mid]
Если названное число было слишком мало, то переменная low обновляется соответственно:
if guess < item:
low = mid + 1
А если догадка была слишком велика, то обновляется переменная high. Полный код выглядит так:
def binary_search(list, item):
low = 0 В переменных low и high хранятся границы той части списка, в которой выполняется поиск
high = len(list)—1
while low <= high: Пока эта часть не сократится до одного элемента …
mid = (low + high)/2 … проверяем средний элемент
guess = list[mid]
if guess == item: Значение найдено
return mid
if guess > item: Много
high = mid - 1
else: Мало
low = mid + 1
return None Значение не существует
my_list = [1, 3, 5, 7, 9] А теперь протестируем функцию!
print binary_search(my_list, 3) # => 1 Вспомните: нумерация элементов начинается с 0. Второй ячейке соответствует индекс 1
print binary_search(my_list, -1) # => None "None" в Python означает "ничто". Это признак того, что элемент не найден
Упражнения
1.1 Имеется отсортированный список из 128 имен, и вы ищете в нем значение методом бинарного поиска. Какое максимальное количество проверок для этого может потребоваться?
1.2 Предположим, размер списка увеличился вдвое. Как изменится максимальное количество проверок?
Время выполнения
Каждый раз, когда мы будем рассматривать очередной алгоритм, я буду обсуждать время его выполнения. Обычно следует выбирать самый эффективный алгоритм, будь то оптимизация по времени или памяти.
Вернемся к бинарному поиску. Сколько времени сэкономит его применение? В первом варианте мы последовательно проверяли каждое число, одно за другим. Если список состоит из 100 чисел, может потребоваться до 100 попыток. Для списка из 4 миллиардов чисел потребуется до 4 миллиардов попыток. Таким образом, максимальное количество попыток совпадает с размером списка. Такое время выполнения называется линейным.
С бинарным поиском дело обстоит иначе. Если список состоит из 100 элементов, потребуется не более 7 попыток. Для списка из 4 миллиардов элементов потребуется не более 32 попыток. Впечатляет, верно? Бинарный поиск выполняется за логарифмическое время. В следующей таблице приводится краткая сводка результатов.
Время выполнения алгоритмов поиска
«O-большое»
Специальная нотация «O-большое» описывает скорость работы алгоритма. Зачем вам это? Время от времени вам придется использовать чужие алгоритмы, а потому неплохо было бы понимать, насколько быстро или медленно они работают. В этом разделе я объясню, что представляет собой «O-большое», и приведу список самых распространенных вариантов времени выполнения для некоторых алгоритмов.
