На этом шаге обсудим время выполнения алгоритма бинарного поиска.
Независимо от "статуса" решаемой задачи нужно выбирать самый эффективный алгоритм, будь то оптимизация по времени или памяти.
Посмотрим, сколько времени экономит применение бинарного поиска. Вернемся к задаче с угадыванием числа от 1 до 100.
В первом случае, Лиза перечисляла все значения от 1 до того момента, пока не угадает. Максимальное количество попыток - 100. Если список из 1 миллиарда чисел, то потребуется до 1 миллиарда попыток. Т.е. максимальное количество попыток совпадает с размером списка. Такое время выполнения называется линейным.
Если список состоит из 100 элементов, то с применением алгоритма бинарного поиска потребуется не более 7 попыток для угадывания числа. Для списка из 1 миллиарда элементов потребуется не более 30 попыток. Т.е. бинарный поиск выполняется за логарифмическое время.
Сводка результатов приведена на рис. 1.
Рис.1. Время выполнения алгоритмов поиска
Допустим, проверка одного элемента занимает 1 миллисекунду (мс). При простом поиске Лизе придется проверить 100 элементов, поэтому поиск займет 100 мс. С другой стороны, при бинарном поиске достаточно проверить всего 7 элементов (log2100 равен приблизительно 7), а поиск займет 7 мс. Но реальный список может содержать более миллиарда элементов. Сколько времени в таком случае потребуется для выполнения простого и бинарного поиска?
Сводка результатов приведена на рис. 2.
Рис.2. Изменение времени выполнения алгоритмов поиска
С увеличением количества элементов бинарный поиск занимает чуть больше времени. А простой поиск займет гораздо больше времени. Таким образом, с увеличением списка бинарный поиск начинает работать гораздо быстрее простого.
Недостаточно знать, сколько времени должен работать алгоритм, - необходимо знать, как возрастает время выполнения с ростом размера списка. Здесь нам пригодится "О-большое".
На следующем шаге рассмотрим понятие "О-большое".
