о 2.43 Решите рекурсию

0= (C/2) при Л> 2 и d = 1, когда является степенью числа 2.

2.44 Решите рекурсию

Cn/2 при > 2 и Ci = 1,

когда является степенью числа 2.

2.45 Рассмотрите семейство рекурсий наподобие формулы 2.1, где N/2 может означать Ln/2] или In/2\ и единственное требование заключается в том, чтобы рекурсия имела место при N > cq и Cs - 0{\) при < cq. Докажите, что решением всех таких рекурсий является формула \gN + 0(1).

2.46 Выведите обобщенные рекурсии и их решения, как в упражнении 2.45, для формул 2.2-2.5.

2.6 Примеры алгоритмического анализа

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

Например, представим себе компанию, обрабатывающую кредитные карточки и имеющую N рискованных или украденных кредитных карточек. При этом компании необходимо проверять, нет ли среди М транзакций какого-либо из этих плохих номеров. Для общности необходимо считать TV большим (скажем, порядка 10-10), а Л/ - огромным (порядка 10-10). Цель анализа заключается в приблизительной оценке времен выполнения алгоритмов, когда параметры принимают значения из указанного диапазона.

Программа 2.1 реализует прямое решение проблемы поиска. Она оформлена как функция С++, обрабатывающая массив (см. главу 3), для совместимости с другими вариантами кода для этой задачи, которые мы исследуем в части 4. Однако необязательно вдаваться в детали программы для понимания алгоритма: мы сохраняем все объекты в массиве, затем для каждой транзакции мы последовательно просматриваем массив от начала до конца, проверяя, содержится ли в нем нужный номер.

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

Программа 2.1 Последовательный поиск

Данная функция проверяет, находится ли число v среди элементов массива а[1], а[1+1], а[г] путем последовательного сравнения с каждым элементом, начиная с начала. Если по достижении последнего элемента нужное значение не найдено, то функция возвращает значение -1. Иначе она возвращает индекс элемента массива, содержащего искомое число.

int search(int а[] , int v, int 1, int r) {

for (int i = 1; i <= r; i++)

if (v == a[i]) return i; return -1;

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

Однако, чтобы сделать какой-либо прогноз, необходимо высказать предположение о данных. В данном случае предположим, что все числа выбраны случайным образом. Из него следует, например, что каждое число в таблице может с одинаковой вероятностью оказаться предметом поиска. После некоторых размышлений мы приходим к выводу, что именно это свойство поиска является наиболее важным, потому что среди случайно выбранных чисел может вообще не происходить успешного поиска (см. упражнение 2.48). В некоторых приложениях количество транзакций с успешным поиском может быть высоким, в других приложениях - низким. Чтобы не запутывать модель свойствами приложения, мы разделим задачу на два случая (успешный и неуспешный поиск) и проанализируем их независимо. Данный пример иллюстрирует, что важным моментом эффективного анализа является разработка разумной модели приложения. Наши аналитические результаты будут зависеть от доли успешных поисков, более того, они обеспечат нас информацией, необходимой для выбора различных алгоритмов для разных приложений на основании этого параметра.

Лемма 2.1 Последовательный поиск исследует N чисел при каждом неуспешном поиске и в среднем порядка N/2 чисел при каждом успешном поиске.

Если каждое число в таблице с равной вероятностью может быть объектом поиска, тогда

(1 + 2 + ... + 7V)/7V = (7V+ 1)/2 является средней ценой поиска.

Лемма 2.1 подразумевает, что время выполнения программы 2.1 пропорционально Л, предмет неявного допущения, что средняя цена сравнения двух чисел постоянна. Таким образом, например, можно ожидать, что если удвоить количество объектов, то и время, необходимое для поиска, также удвоится.

Последовательный поиск в неуспешном случае можно ускорить, если упорядочить числа в таблице. Сортировка чисел в таблице является предметом рассмотрения глав 6-11. Несколько алгоритмов, которые мы рассмотрим, выполняют эту задачу за время, пропорциональное logTV, которое незначительно по сра1внению с ценой поиска при очень больших М. В упорядоченной таблице можно прервать поиск сразу по достижении числа, большего, чем искомое. Такое изменение уменьшает цену последовательного поиска до N/ 2 чисел, которые необходимо в среднем проверить при неуспешном поиске. Время для такого случая совпадает со временем для успешного поиска.

Лемма 2.2 Алгоритм последовательного поиска в упорядоченной таблице проверяет N чисел для каждого поиска в худшем случае и порядка N/2 чисел в среднем.

Здесь все еще необходимо определить модель неуспешного поиска. Этот результат следует из предположения, что поиск может с равной вероятностью закончится на любом из 7V + 1 интервалов, задаваемых числами в таблице, а это непосредственно приводит к выражению

{I + 2 + ... + N+ N)/N = {N+ 3)/2.

Цена неуспешного поиска, который заканчивается до или после Л-ой записи в таблице, такая же: N.

Другой способ выразить результат леммы 2.2 - это сказать, что время выполнения последовательного поиска пропорционально MN для М транзакций в среднем и худшем случае. Если мы удвоим или количество транзакций, или количество объектов в таблице, то время выполнения удвоится; если мы удвоим обе величины одновременно, тогда время выполнения вырастет в 4 раза. Этот результат свидетельствует о том, что данный метод не подходит для очень больших таблиц. Если для проверки одного числа требуется с микросекунд, а М = и N - 10, тогда время выполнения для всех транзакций будет, по крайней мере, (с/2)10 секунд, или, следуя рис. 2.1, около 16с лет, что совершенно не подходит.

Программа 2.2 Бинарный поиск

Эта программа обладает такой же функциональностью, что и программа 2.1, но гораздо эффективнее.

int search(int а[], int v, int 1, int r) {

while (r >= 1) { int m = (l+r)/2;

if (v == a[m]) return m;

if (v < a[m]) r = m-1; else 1 = m+1 ;

return -1;

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