чит, поиск прошел успешно, если искомое число меньше, то мы применим такой же метод к левой части таблицы, если больше - то к правой. На рис. 2.7 представлен пример выполнения этого метода над набором чисел.

Лемма 2.3 Бинарный поиск исследует не более .IgAj + 1 чисел.

Доказательство данной леммы иллюстрирует применение рекуррентных соотношений при анализе алгоритмов. Пусть 7V - это количество сравнений, необходимое бинарному поиску в худшем случае, тогда из того, что алгоритм сводит поиск в таблице размера к поиску в два раза меньшей таблице, непосредственно следует, что

Tn < tin/2\ + 1, при ЛГ> 2 и л = 1.

При поиске в таблице размером N мы проверяем число посредине, затем производим поиск в таблице размером не более \.N/2\. Реальная цена может быть меньше этого значения, так как сравнение может закончиться успешно или таблица будет иметь размер VN/2J - 1 (если четно). Так же, как это было сделано в решении формулы 2.2, легко доказать, что < п + \ при N = 2 , а затем получить общий результат с помощью индукции.

Лемма 2.3 позволяет решить очень большую задачу с 1 миллионом чисел при помощи 20 сравнений на транзакцию, а это обычно время, меньшее, чем требуется для чтения или записи числа на большинстве современных компьютеров. Проблема поиска настолько важна, что было разработано несколько методов еще более быстрых, чем приведенный здесь, как будет показано в главах 12-16.

Отметьте, что леммы 2.1 и 2.2 выражены через операции, наиболее часто выполняемые над данными. Как отмечено в комментарии, следующем за леммой 2.1, ожидается, что каждая операция должна занимать постоянное время, тогда можно заключить, что время выполнения бинарного поиска пропорционально IgA, в отличие от для последовательного поиска. При удвоении N время бинарного поиска изменяется, но не удваивается, как это имеет место для последовательного поиска. С ростом разница между двумя методами растет.

Можно проверить аналитическое доказательство лемм 2.1 и 2.2, написав программу и протестировав алгоритм. Например, в табл. 2.4 показаны времена выполнения

РИСУНОК 2.7 БИНАРНЫЙ ПОИСК

Чтобы проверить, содержится ли число 5025 в таблице, приведенной в левой колонке, мы сначала сравниваем его с 6504, из чего следует, что дальше необходимо рассматривать первую половину массива. Затем производится сравнение с числом 4548 (середина первой половины), после чего исследуется вторая половина первой половины. Мы продолжаем этот процесс, работая с подмассивом, в котором может содержаться искомое число, если оно есть в таблице. В заключение мы получаем подмассив с одним элементом, не равным 5025, из чего следует, что 5025 в таблице не содержится.

бинарного и последовательного поиска для М поисков в таблице размером N (включая в случае бинарного поиска и цену сортировки таблицы) при различных значениях М и N. Здесь мы не будем рассматривать реализаций программы и детальные эксперименты, поскольку похожие задачи полностью рассмотрены в главах 6 и 11, а, кроме того, использование библиотечных и внешних функций и другие детали создания программ из компонент, включая и функцию sort, объясняются в главе 3. В данный момент мы просто подчеркнем, что проведение эмпирического тестирования - это неотъемлемая часть оценки эффективности алгоритма.

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

Таблица 2.4 Эмпирическое изучение последовательного и бинарного поиска

Приведенные ниже относительные времена выполнения подтверждают наши аналитические результаты, что в случае М поисков в таблице из N объектов время последовательного поиска пропорционально MN, а время бинарного поиска - М \gN. При удвоении N время последовательного поиска также удваивается, а время бинарного поиска почти не изменяется. Последовательный поиск неприменим для очень больших М при растущих N, а бинарный поиск является достаточно быстрым даже для огромных таблиц.

Значения:

S последовательный поиск (программа 2.1) В бинарный поиск (программа 2.2)

Данный пример является прототипом общего подхода к сравнению алгоритмов. Математический анализ используется для оценки частоты, с которой алгоритм производит абстрактные операции, затем на основе этих результатов выводится функциональная форма времени выполнения, которая позволяет проверить и расширить эмпирические данные. По мере нахождения алгоритмических решений все более и более тонких вычислительных задач и усложняющемся математическом анализе свойств их производительности, мы будем обращаться к литературе за математическими результатами, чтобы основное внимание в книге уделить самим алгоритмам. Здесь нет возможности производить тщательное математическое и эмпирическое изучение всех алгоритмов, а главной задачей является определение наиболее существенных характеристик производительности. При этом, в принципе, всегда можно разработать научную основу, необходимую для правильного выбора алгоритмов для важных приложений.

Упражнения

t> 2.47 Найдите среднее число сравнений, используемых программой 2.1, если aN поисков прошли успешно, а О < а < 1.

2.48 Оцените вероятность того, что хотя бы одно из М случайных десятизначных чисел будет содержаться в наборе из TV чисел, при Л/= 10, 100, 1000 и N = 10 Ю, 10 10

2.49 Напишите программу, которая генерирует М целых чисел и помещает их в массив, затем подсчитывает количество N целых чисел, которые совпадают с одним из чисел массива, используя последовательный поиск. Запустите программу при М= 10, 100, 1000 и 7V= 10, 100, 1000.

2.50 Сформулируйте и докажите лемму, аналогичную лемме 2.3 для бинарного поиска.

2.7 Гарантии, предсказания и ограничения

Время выполнения большинства алгоритмов зависит от входных данных. Обычно нашей целью при анализе алгоритмов является исключить каким-либо образом эту зависимость: необходимо иметь возможность сказать что-то о производительности наших программ, что почти не зависит от входных данных, так как в общем случае неизвестно, какими будут входные данные при каждом новом запуске программы. Примеры из раздела 2.6 иллюстрируют два основных подхода, которые применяются в этом случае: анализ низкой производительности и анализ средней производительности.

Изучение низкой производительности алгоритмов достаточно привлекательно, поскольку оно позволяет гарантировать что-либо о времени выполнения программ. Мы говорим, что частота, с которой запускаются определенные абстрактные операции, меньше, чем определенная функция от количества вводов, независимо от того, какими являются входные значения. Например, лемма 2.3 - пример такой гарантии для бинарного поиска, так же как лемма 1.3 - для взвешенного быстрого объединения. Если гарантии являются низкими, как в случае с бинарным поиском, тогда это благоприятная ситуация, поскольку удалось устранить ситуации, когда программа