Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - страница 6

my_list = [1, 3, 5, 7, 9] А теперь протестируем функцию!

print binary_search(my_list, 3) # => 1 Вспомните: нумерация элементов начинается с 0. Второй ячейке соответствует индекс 1

print binary_search(my_list, -1) # => None

1.1 Имеется отсортированный список из 128 имен, и вы ищете в нем значение методом бинарного поиска. Какое максимальное количество проверок для этого может потребоваться?

1.2 Предположим, размер списка увеличился вдвое. Как изменится максимальное количество проверок?

Время выполнения

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

Вернемся к бинарному поиску. Сколько времени сэкономит его применение? В первом варианте мы последовательно проверяли каждое число, одно за другим. Если список состоит из 100 чисел, может потребоваться до 100 попыток. Для списка из 4 миллиардов чисел потребуется до 4 миллиардов попыток. Таким образом, максимальное количество попыток совпадает с размером списка. Такое время выполнения называется линейным.

С бинарным поиском дело обстоит иначе. Если список состоит из 100 элементов, потребуется не более 7 попыток. Для списка из 4 миллиардов элементов потребуется не более 32 попыток. Впечатляет, верно? Бинарный поиск выполняется за логарифмическое время. В следующей таблице приводится краткая сводка результатов.

Время выполнения алгоритмов поиска

Специальная нотация «O-большое» описывает скорость работы алгоритма. Зачем вам это? Время от времени вам придется использовать чужие алгоритмы, а потому неплохо было бы понимать, насколько быстро или медленно они работают. В этом разделе я объясню, что представляет собой «O-большое», и приведу список самых распространенных вариантов времени выполнения для некоторых алгоритмов.

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

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

Это один из примеров того, как время выполнения двух алгоритмов растет с разной скоростью. Боб пытается выбрать между простым и бинарным поиском. Его алгоритм должен работать быстро и правильно. С одной стороны, бинарный поиск работает быстрее. У Боба есть всего 10 секунд, чтобы выбрать место посадки; если он не уложится в это время, то момент для посадки будет упущен. С другой стороны, простой поиск пишется проще и вероятность ошибок в нем ниже… Конечно, Боб совершенно не хочет допустить ошибку в коде посадки ракеты. И тогда для пущей уверенности Боб решает измерить время выполнения обоих алгоритмов для списка из 100 элементов.

Допустим, проверка одного элемента занимает 1 миллисекунду (мс). При простом поиске Бобу придется проверить 100 элементов, поэтому поиск зай­мет 100 мс. С другой стороны, при бинарном поиске достаточно проверить всего 7 элементов (log2100 равен приблизительно 7), а поиск займет 7 мс. Но реальный список может содержать более миллиарда элементов. Сколько времени в таком случае потребуется для выполнения простого поиска? А при бинарном поиске? Обязательно ответьте на оба вопроса, прежде чем продолжить чтение.

Время выполнения простого и бинарного поиска для списка из 100 элементов

Боб проводит бинарный поиск с 1 миллиардом элементов, и на это уходит 30 мс (log21 000 000 000 равен приблизительно 30). «32 мс! — думает Боб. — Бинарный поиск в 15 раз быстрее простого, потому что простой поиск для 100 элементов занял 100 мс, а бинарный поиск занял 7 мс. Значит, простой поиск займет 30 × 15 = 450 мс, верно? Гораздо меньше отведенных 10 секунд». И Боб выбирает простой поиск. Верен ли его выбор?

Нет, Боб ошибается. Глубоко ошибается. Время выполнения для простого поиска с 1 миллиардом элементов составит 1 миллиард миллисекунд, а это 11 дней! Проблема в том, что время выполнения для бинарного и простого поиска растет с разной скоростью.

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