Ю.Ю. Громов и др. Информатика (2007)

Рис. 4.10. Сортировка списка имен Fred, Alice, David, Bill и Carol

В этом варианте два верхних имени образуют отсортированный подсписок, а три верхних – нет. Подымем третью карточку с именем David, опустим карточку с именем Fred вниз, туда, где только что была карточка с именем David, а затем поместим карточку с именем David в ту позицию, которую раньше занимала карточка с именем Fred, как показано во второй строке на рис. 4.10. Теперь три верхних элемента списка образуют отсортированный подсписок. Продолжая действовать таким способом, мы можем получить список, в котором будут отсортированы четыре верхних элемента. Для этого нужно поднять четвертую карточку с именем Bill, опустить вниз карточки с именами Fred и David, а затем поместим карточку с именем Bill в освободившуюся позицию (третья строка на рис. 4.10). И наконец, чтобы завершить процесс сортировки, необходимо поднять карточку с именем Carol, опустить вниз карточки с именами Fred и David, а затем поместить карточку с именем Carol в освободившуюся позицию – как показано в четвертой строке на рис. 4.10.

Теперь наша задача состоит в том, чтобы проанализировать процесс сортировки конкретного списка и попытаться обобщить его в целях получения алгоритма сортировки любого списка. С этой точки зрения каждая строка на рис. 4.10 представляет собой один и тот же повторяющийся процесс: "Поднять карточку с именем, первую в неотсортированной части списка, сдвинуть вниз карточки с именами, которые находятся ниже по алфавиту, чем имя на взятой нами карточке, а затем поместить эту взятую карточку на освободившееся место в списке". Если назвать выбранное имя опорным элементом, то с помощью нашего псевдокода данный процесс можно описать следующим образом:

Переместить ОпорныйЭлемент во временное хранилище, оставив в списке пустое место; while (над пустым местом есть имя, и оно > ОпорныйЭлемент) do

{переместить имя, находящееся над пустым местом, вниз, оставив в его прежней позиции пустое место}

Поместить ОпорныйЭлемент на пустое место в списке

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

N ← 2;

while (N ≤ ДлинаСписка) do

{выбрать N-й элемент как ОпорныйЭлемент;

.

.

.

N ← N + 1}

Здесь N – счетчик, параметр ДлинаСписка – количество элементов в списке, а точки указывают место, где должна располагаться составленная нами выше процедура.

Полный текст программы сортировки на языке псевдокода приведен на рис. 4.11. Не вдаваясь в подробности, можно сказать, что эта программа сортирует список, многократно повторяя следующие действия: "Элемент извлекается из списка, а затем вставляется на надлежащее ему место". Именно по причине многократного повторения вставки элементов в список данный алгоритм получил название сортировки методом вставки (insertion sort).

Обратите внимание, что представленная на рис. 4.11 структура содержит Цикл, помещенный внутрь другого цикла. Внешний цикл представлен первой инструкцией while, а внутренний цикл – второй инструкцией while. Каждое выполнение тела внешнего цикла приводит к тому, что внутренний цикл инициализируется и выполняется до тех пор, пока не будет выполнено условие его окончания. Таким образом, однократное выполнение тела внешнего цикла будет сопровождаться многократным выполнением тела внутреннего цикла.

procedure Сортировка (Список) N ← 2;

while (N ≤ ДлинаСписка) do

{выбрать N-й элемент как ОпорныйЭлемент; переместить ОпорныйЭлемент во временное

хранилище, оставив в списке пустое место;

while (над пустым местом есть имя, и оно > ОпорныйЭлемент) do

{переместить имя, находящееся над пустым местом, вниз,

оставив в его прежней позиции пустое

место}

поместить ОпорныйЭлемент на пустое место в

списке;

N ← N + 1}

Рис. 4.11. Алгоритмсортировкиметодомвставки, написанныйнапсевдокоде

При инициализации управления внешним циклом начальное значение счетчика N устанавливается с помощью инструк-

ции

N ← 2;

Операция модификации этого цикла включает увеличение значения счетчика N в конце тела цикла с помощью инструкции

N ← N + 1.

Условие окончания внешнего цикла выполняется, когда значение счетчика N превысит длину сортируемого списка. Управление внутренним циклом инициализируется, когда опорный элемент извлекается из списка и в нем образуется

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

Вопросы для самопроверки

1.Преобразуйте показанную на рис. 4.6 процедуру последовательного поиска так, чтобы она могла работать с неотсортированными списками.

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

repeat-until.

Z ← 0;

X ← 1;

while (X < 6) do

{Z ← Z + X;

X ← X + 1}

3.Предположим, что процедура сортировки методом вставки, представленная на рис 4.11, была применена к списку George, Cheryl, Alice и Bob. Опишите, как будет выглядеть список каждый раз по окончании выполнения тела внешней структуры while.

4.Почему не следует заменять фразу "по алфавиту размещается ниже" в инструкции while на рис. 4.11 на

фразу "по алфавиту размещается ниже или эквивалентно"?

5.Вариантом алгоритма сортировки методом вставки является выборочная сортировка (selection sort). Каждый раз выбирается наименьший элемент списка и помещается на первое место. Затем выбирается наименьший элемент из оставшихся элементов списка и помещается на второе место в списке. Многократно выбирая наименьший элемент из оставшейся части списка и перемещая его вперед, мы увеличиваем отсортированную часть списка, находящуюся вначале, тогда как его конечная часть, состоящая из неотсортированных элементов, сжимается. С помощью нашего псевдокода напишите процедуру сортировки списка с использованием алгоритма выборочной сортировки, аналогичную процедуре, представленной на рис. 4.11.

6.Другой известный алгоритм сортировки – сортировка методом пузырька (bubble sort). Он основан на процессе повторяющегося сравнения двух стоящих рядом имен и перестановки их местами, если они находились относительно друг

друга в порядке, отличном от требуемого. Предположим, что сортируемый список состоит из n элементов. Сортировка методом пузырька начнется сравнением (и, возможно, перестановкой) элементов, стоящих на местах n и n – 1. Затем сравниваются элементы, стоящие на местах n – 1 и n – 2, и так далее в направлении к началу списка, пока не будет выполнено сравнение (и, возможно, перестановка) первого и второго элементов списка. В результате прохождения по всему списку его наименьший элемент будет вынесен на первое место. Аналогичным образом, после второго прохождения списка следующий по величине элемент будет вынесен на второе место и т.д. Таким образом, пройдя список n – 1 раз, мы отсортируем его целиком. (Если визуально представить себе работу данного алгоритма, то создается впечатление, что наименьшие из оставшихся неупорядоченных элементов списка последовательно всплывают к его вершине как пузырьки, – отсюда и название алгоритма.) Используя наш псевдокод, напишите процедуру сортировки списка методом пузырька по аналогии с процедурой, представленной на рис. 4.11.

4.5. РЕКУРСИВНЫЕ СТРУКТУРЫ

Рекурсивные структуры являются другим видом повторяющихся структур. Цикл означает повторное выполнение набора команд, при этом весь набор команд полностью выполняется, а затем повторяется. Рекурсия же предполагает повторное выполнение набора команд как подзадачу самой себя. Чтобы ввести понятие рекурсии, рассмотрим алгоритм двоичного поиска (binary search), в котором в процессе поиска применяется метод разбиения.

Поиск и сортировка. Алгоритмы последовательного и двоичного поиска – это всего лишь два представителя из большого семейства алгоритмов, осуществляющих поисковый процесс. (Использование для этой цели индексов и механизм перемешивания будет рассматриваться в главе 8.) Аналогично, сортировка методом вставки – это лишь один из многих существующих алгоритмов сортировки. Другими классическими алгоритмами являются сортировка слиянием (обсуждается в главе 11), выборочная сортировка (ее описание можно найти в подразделе "Вопросы для самопроверки", п. 5 раздела 4.4), сортировка методом пузырька (см. подраздел "Вопросы для самопроверки", п. 6, раздела 4.4), быстрая сортировка (применяющая к процессу сортировки принцип "разделяй и властвуй") и древовидная сортировка (использующая искусную методику для нахождения элементов, которые следует переместить вверх по списку).

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

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

На рис. 4.12 этот подход, применяемый к произвольному отсортированному списку, описан с помощью псевдокода. В данном случае мы не знаем примерного места расположения элементов, поэтому инструкции на рисунке предписывают начинать работу с открытия списка на "среднем" элементе. Слово "средний" заключено в кавычки, поскольку вполне возможно, что число элементов в списке будет четным, и тогда среднего элемента в строгом смысле этого слова просто не существует. В этом случае условимся, что средним считается первый элемент второй половины списка.

выбрать “средний” элемент как ПроверяемоеЗначение; выполнить набор команд, соответствующий одному из

случаев:

Случай 1: ИскомоеЗначение = ПроверяемоеЗначение {сообщить об успехе}

Случай 2: ИскомоеЗначение < ПроверяемоеЗначение {применить процедуру Поиск для обнаружения ИскомоеЗначение в верхней части Списка, и сообщить о результате этого поиска}

Случай 3: ИскомоеЗначение > ПроверяемоеЗначение {применить процедуру Поиск для обнаружения ИскомоеЗначение в нижней части Списка, и сообщить о результате этого поиска}

Рис. 4.12. Принцип двоичного поиска

Если выбранный элемент не является искомым, то программа, приведенная на рис. 4.12, предлагает два варианта дальнейших действий (поиск или в начальной или конечной половине списка). В каждом из них предусматривается выполнения вторичного поиска, осуществляемого процедурой с именем Search. Следовательно, чтобы завершить нашу программу, необходимо создать подобную процедуру, описывающую, как осуществляется этот вторичный поиск. Заметим, что эта процедура должна быть в состоянии удовлетворить запрос на поиск в пустом списке. Например, если показанной на рис. 4.12 программе будет передан список, состоящий из одного элемента, который не является искомым, то процедура Search будет вызвана для поиска либо в подсписке, находящемся выше этого единственного значения, либо в подсписке, находящемся ниже его, однако оба эти списка пусты.

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

ска, ииспользовалегодлядальнейшегосужения областипоиска.

Подобный подход к процедуре поиска представлен на рис. 4.13. Здесь демонстрируется способ решения задачи, заключающейся в определении присутствия имени John в списке, приведенном в левой части рисунка. Прежде всего, анализируется средний элемент Harry. Так как имя, которое мы ищем, по алфавиту располагается после данного имени, поиск продолжается в нижней части исходного списка. Средним элементом этой части является имя Larry. Поскольку по алфавиту искомое имя предшествует данному, поиск следует продолжать в верхней части текущего подсписка. Обратившись к среднему элементу этого вторичного подсписка, обнаруживаем искомое имя John и объявляем поиск успешным. Короче говоря, наша стратегия состоит в последовательном делении анализируемого списка на меньшие по размеру сегменты до тех пор, пока либо будет найдено искомое значение, либо поиск сузится до пустого сегмента.

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

Рис. 4.13. Применение стратегии двоичного поиска для обнаружения имени John в упорядоченном списке

Чтобы увидеть, как представленная на рис. 4.14 процедура выполняет свою задачу, попробуем с ее помощью определить, содержится ли значение Bill в списке имен Alice, Bill, Carol, David, Evelyn, Fred, George. Поиск начинается с выбора в качестве проверяемого элемента имени David (среднего элемента списка). Так как искомое значение (Bill) по алфавиту предшествует проверяемому, следует применить процедуру Search к списку элементов, предшествующих имени David, т.е. к списку Alice, Bill, Carol. Для этого нам потребуется создать

Procedure Поиск (Список, ИскомоеЗначение) if (Список пустой)

then {сообщить о неудаче}

else {выбрать “средний” элемент как ПроверяемоеЗначение;выполнить набор команд, соответствующий одному из случаев:

Случай 1: ИскомоеЗначение = ПроверяемоеЗначение {сообщить об успехе}

Случай 2: ИскомоеЗначение < ПроверяемоеЗначение {применить процедуру Поиск для обнаружения ИскомоеЗначение в верхней части Списка, и сообщить о результате этого поиска}

Случай 3: ИскомоеЗначение > ПроверяемоеЗначение {применить процедуру Поиск для обнаружения ИскомоеЗначение в нижней части Списка, и сообщить о результате этого поиска}

}

Рис. 4.14. Алгоритм двоичного поиска, записанный на псевдокоде

вторую копию процедуры Search, предназначенную для решения данной промежуточной задачи.

Теперь мы имеем две выполняющиеся копии нашей процедуры поиска, как показано на рис. 4.15. Дальнейшее выполнение исходнойкопиипроцедурывременно приостановлено наследующейинструкции:

Применить процедуру Search, чтобы определить, есть ли в части списка, предшествующей элементу <проверяемый_элемент>, элемент <искомое_значение>

Вторая копия процедуры используется для поиска имени Bill в списке Alice, Bill, Carol. Завершив вторую процедуру двоичного поиска, мы аннулируем ее копию и сообщим полученные в ней результаты исходной копии, после чего выполнение исходной копии будет продолжено с указанного места. Таким образом, вторая копия процедуры функционирует как подчиненная исходной, выполняя задачу, запрошенную исходной копией, а затем исчезая.

Вторичная процедура поиска выбирает имя Bill в качестве проверяемого значения, так как это средний элемент в списке Alice, Bill, Carol. Поскольку он совпадает с искомым значением, поиск объявляется успешным и вторичная процедура завершает свою работу.

Рис. 4.15. Вызов второй копии процедуры из ее исходной копии при поиске записи Bill

Evelyn

Fred

George

Рис. 4.16. Вызов второй копии процедуры из ее исходной копии при поиске записи David

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

Alice, Bill, Carol, David, Evelyn, Fred, George.

Теперь давайте посмотрим, что произойдет, если перед представленной на рис. 4.14 процедурой поставить задачу определить наличие в списке Alice, Carol, Evelyn, Fred, George элемента David. На этот раз исходная копия процедуры выбирает в качестве проверяемого значения имя Evelyn и определяет, что искомое значение должно находиться в предшествующей части списка. Поэтому она вызывает еще одну копию процедуры для поиска в списке тех элементов, которые стоят перед именем Evelyn, т.е. в двухэлементном списке, состоящем из имен Alice и Carol. Ситуация на этой стадии выполнения алгоритма представлена на рис. 4.16.

Вторая копия процедуры выберет в качестве проверяемого элемента имя Carol и определит, что искомое значение должно находиться после него. Процедура вызовет третью копию процедуры "Поиск" для поиска требуемого элемента в списке имен, следующих за именем Carol в списке Alice, Carol. Однако этот список пуст и перед третьей копией процедуры стоит задача поиска искомого значения David в пустом списке. Исходная копия процедуры осуществляет поиск требуемого элемента в списке Alice, Carol, Evelyn, Fred, George, выбрав в качестве проверяемого имя Evelyn; вторая копия процедуры занята поиском требуемого элемента в списке Alice, Carol, выбрав в качеству проверяемого элемент Carol; а третья начинает поиск в пустом списке.

Конечно же, третья копия процедуры тут же объявляет свой поиск неудачным и завершается. После этого вторая копия может продолжить свою работу. Она обнаруживает, что запрошенный поиск оказался неуспешным, поэтому также объявляет свой поиск неудачным и завершается. Исходная копия процедуры, ожидавшая поступления сообщения от второй копии, теперь может продолжить свою работу. Так как запрошенный поиск оказался неудачным, она тоже объявляет свой поиск неудачным, после чего завершается. Таким образом, наша программа пришла к правильному заключению, что имя David не содержится в списке имен Alice, Carol, Evelyn, Fred, George.

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

Управление рекурсией. Алгоритм двоичного поиска похож на алгоритм последовательного поиска, так как каждый из них предусматривает выполнение повторяющегося процесса. Однако реализация этого повторения в каждом случае существенно отличается. При последовательном поиске повторение организуется с помощью цикла, в случае двоичного поиска каждая стадия повторенияреализуется какподзадачапредыдущейстадии. Этотметодповторения известенкакрекурсия (recursion).

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

Будучи повторяющимися процессами, рекурсивные структуры почти так же зависят от корректного управления, как и циклические структуры. Как и в случае управления циклами, рекурсивные системы зависят от проверки условия окончания

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

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

procedure FindExit (<лабиринт>)

Продвигаться по лабиринту до развилки, тупика или выхода; В каждом из указанных случаев вы-

и выход еще не найден) do

(применить процедуру FindExit к лабиринту, представленному одной из неисследованных ветвей;

if (эта процедура сообщила, что выход найден) then (сообщить "выход найден".)

)

if (все варианты этой развилки неудачны) then (сообщить "неудача")

)

Обычно рекурсивная программа разрабатывается так, чтобы проверять условие окончания (часто называемое граничным условием, или условием вырождения) до того, как будут вызваны последующие активации. Если условие окончания еще не достигнуто, то программа создает следующую свою активацию, задача которой – найти решение сокращенной версии задачи текущей активации. Подразумевается, что эта сокращенная версия находится ближе к условию окончания, чем задача, которой занимается текущая активация. Как только условие окончания будет обнаружено, выбирается путь, вызывающий завершение текущей активации без создания дополнительных активаций. Это означает, что одной из остановленных активаций разрешается продолжить свое выполнение, завершить ее задачу и, в свою очередь, позволить следующей остановленной активации возобновить свои действия. Таким образом, все порожденные активации в конечном счете будут завершены, что приведет к завершению исходной задачи.

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

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

Вопросы для самопроверки

1.Какие имена будут проверены программой двоичного поиска (рис. 4.14) при поиске имени Joe в списке имен Alice, Bob, Carol, David, Evelyn, Fred, George, Henry, Irene, Joe, Karl, Larry, Mary, Nancy и Oliver?

2.Какое максимальное количество элементов может потребоваться проверить при выполнении двоичного поиска в списке из 200 элементов? В списке из 100 000 элементов?

4.6.ЭФФЕКТИВНОСТЬ И ПРАВИЛЬНОСТЬ

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

них всегда нужно помнить при самостоятельной разработке алгоритмов. Первое из них – эффективность, а второе – правильность.

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

Рассмотрим задачу, с которой сталкивается секретарь университета при поиске личных дел студентов и их заполнении. Хотя в университете на протяжении любого семестра фактически числится около 10 000 студентов, секретарю в действительности приходится иметь дело с более чем 30 000 личных дел, поскольку за несколько предыдущих лет многие из студентов зарегистрировались для изучения хотя бы одной из преподаваемых в университете дисциплин, но не смогли закончить цикл обучения. Теперь предположим, что все личные дела хранятся в компьютере секретаря в виде списка, упорядоченного по идентификационным номерам каждого из студентов. Чтобы найти личное дело некоторого студента, секретарь должен выполнить поиск по его идентификационному номеру в общем списке.

Мы уже познакомились с двумя алгоритмами поиска в подобных списках последовательным и двоичным поиском. Сейчас нам нужно дать ответ на вопрос, почувствует ли секретарь разницу между этими двумя алгоритмами? Начнем с рассмотренияпоследовательного поиска.

При заданном идентификационном номере студента алгоритм последовательного поиска начинает работу с начала списка и последовательно сравнивает каждый выбираемый элемент с искомым числом. Не зная, что представляет собой искомое число, мы не можем определить, насколько далеко потребуется просматривать список. Все же можно утверждать, что для множества выполненных операций поиска их средняя глубина будет равна приблизительно половине длины списка, хотя в отдельных случаях поиск потребует меньшего числа операций, а в других – большего. Можно сделать вывод, что при многократном выполнении последовательного поиска на каждый случай в среднем приходится приблизительно 15 000 просмотренных личных дел. Если выборка каждого личного дела из памяти и сравнение его номера с искомым выполняется за десять миллисекунд (десять тысячных долей секунды), то среднее время поиска будет составлять 150 с или две с половиной минуты. Если секретарю придется так долго ожидать появления на экране монитора личного дела интересующего его студента, несомненно, что этот вариант совершенно неприемлем. Даже если время выборки и проверки каждой записи сократить до одной миллисекунды, на поиск личного дела студента все равно потребуется в среднем около 15 с – все еще слишком много для среднего времени ожидания ответа, которое можно считать приемлемым.

В противоположность этому, алгоритм двоичного поиска начинает работу со сравнения искомого значения со средним элементом списка. Если это не искомый элемент, то область поиска сразу же сужается до половины исходного списка, т.е. после проверки среднего элемента списка из 30 000 личных дел алгоритм двоичного поиска в большинстве случаев выберет для дальнейшего рассмотрения только 15 000 дел. После второго этапа область поиска в большинстве случаев сократится до 7500 дел, после третьего – до 3750 и т.д. В результате искомое значение будет найдено при выборе, самое большее, 15 элементов списка, состоящего из 30 000 дел. Таким образом, если каждое выбранное значение обрабатывается за 10 миллисекунд, процесс поиска нужного личного дела потребует не более 0,15 с, а это означает, что с точки зрения секретаря личное дело любого студента будет появляться на экране практически мгновенно. Можно сделать обоснованное заключение, что

выбор между алгоритмом последовательного поиска и алгоритмом двоичного поиска в данном случае имеет большое значение2.

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

В предыдущем случае выполненный нами анализ заключался в оценке средней производительности алгоритма последовательного поиска, а также определении той производительности, которую алгоритм двоичного поиска продемонстрирует в наихудшем случае. Хотя мы рассматривали список определенной длины, несложно обобщить наши рассуждения на случай списка произвольной длины. В частности, при применении к списку из п элементов алгоритму последовательного поиска в среднем потребуется проверить n/2 элементов, тогда как алгоритму двоичного поиска в самом худшем случае потребуется проверить только log2n элементов. (В данном случае выражение log2n представляет логарифм числа п по основанию 2, который показывает, сколько раз число n можно разделить на два.)

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

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

2 Чтобы воспользоваться преимуществами алгоритма двоичного поиска, личные дела студентов должны располагаться в памяти машины таким образом, чтобы можно было извлекать средние записи последовательно уменьшающихся подсписков без чрезмерных усилий. Это можно осуществить, запоминая личные дела в индексированных файлах-структурах, которые будут обсуждаться в главе 8. Кроме того, тех же результатовможнодостичьисиспользованиемхешированныхфайловыхструктур, которыетакжеописываютсявглаве8.

нут конец списка. В самом лучшем случае каждый опорный элемент уже находится на положенном ему месте. Следовательно, чтобы это было обнаружено, его потребуется сравнить только с одним именем. Поэтому в наилучшем случае применение алгоритма сортировки методом вставки к списку из п элементов потребует выполнения n −1 сравнений. (Второй элемент сравнивается с одним элементом (первым), третий элемент – с одним элементом (вторым) и т.д.).

И наоборот, наихудший сценарий имеет место в том случае, когда каждый опорный элемент потребуется сравнивать со всеми впереди стоящими элементами, прежде чем удастся найти правильное место его расположения. Очевидно, что в этом случае исходный список упорядочен в обратном порядке. Первый опорный элемент (второй элемент списка) сравнивается с одним элементом, второй опорный элемент (третий элемент списка) – с двумя элементами и т.д. (рис. 4.17). Следовательно, общее количество сравнений при сортировке списка из n элементов составит 1+2 +3 +...+(n −1), что эквивалентно

n(n −1)/ 2 или 1/2(n2 – n). В частности, для списка из 10 элементов алгоритму сортировки методом вставки в наихудшем слу-

чае потребуется выполнить 45 сравнений.

В среднем при сортировке методом вставки можно ожидать, что каждый опорный элемент потребуется сравнить с половиной предшествующих ему элементов. В этом случае общее количество выполненных сравнений будет вдвое меньше, чем в наихудшем случае, т.е. (1/4)(п2 – п) сравнений для списка длины п. Например, если использовать сортировку методом вставки для упорядочения множества списков из 10 элементов, то среднее число производимых в каждом случае сравнений будет равно 22,5.

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

Рис. 4.17. Работа алгоритма сортировки методом вставки в наихудшем случае

Данный график построен по оценкам работы алгоритма в наихудшем случае, когда, исходя из результатов наших исследований, для списка длиной п требуется выполнить не менее 1/ 2(n2 −n)сравнений элементов. На графике отмечено несколько

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

Рис. 4.18. График зависимости времени сортировки от длины списка при сортировке методом вставки

Выполним аналогичный анализ работы алгоритма двоичного поиска в наихудшем случае. Как было установлено выше, при использовании этого алгоритма для поиска в списке из п элементов потребуется проанализировать не более log2 n элементов. Это позволяет оценить время, необходимое для выполнения алгоритма при различной длине сортируемого списка. На рис. 4.19 представлен график, построенный по результатам данного анализа. На этом графике также отмечены конкретные значения длины списка, возрастающие на одну и ту же величину, и указано соответствующее время выполнения алгоритма. Обратите внимание, что темпы роста времени выполнения алгоритма снижаются по мере увеличения длины списка, т.е. эффективность алгоритма двоичного поиска возрастает с увеличением длины списка.

Основным отличием между графиками, представленными на рис. 4.18 и 4.19, безусловно, является их общая форма. Именно форма графика, а не его индивидуальные особенности, демонстрирует, насколько хорошо данный алгоритм будет справляться с все возрастающими объемами данных. Заметим, что общая форма графика определяется типом отображаемого выражения, а не его конкретными особенностями: все линейные выражения изображаются прямой линией, все квадратичные выражения – параболической кривой, а все логарифмические выражения порождают логарифмическую кривую, подобную представленной на рис. 4.19. Общую форму кривой принято определять простейшим выражением, порождающим кривую данной формы. В частности, параболическая форма обычно определяется выражением n2, а логарифмическая – выражением lgn.

Рис. 4.19. График зависимости времени поиска от длины списка для алгоритма двоичного поиска

Выше было показано, что форма графика, представляющего зависимость времени выполнения алгоритма от объема входных данных, отражает общие характеристики эффективности алгоритма. Поэтому принято классифицировать алгоритмы согласно форме их графиков, построенных для самого неблагоприятного случая. Способ обозначения, используемый для определения этих классов, иногда называют тета-классами. Алгоритмы, графики которых имеют параболическую форму (например, сортировка методом вставки), относятся к классу Θ(n2), алгоритмы, графики которых имеют логарифмическую форму (например, двоичный поиск), – к классу Θ(lgn). Любой алгоритм из тета-класса Θ(lgn) по самой свой сути всегда более эффективен, чем алгоритм из тета-класса Θ(n2).

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

Путешественник, у которого есть золотая цепочка из семи звеньев, должен остановиться в уединенном отеле на семь ночей. Плата за каждую проведенную в отеле ночь составляет одно звено его цепочки. Какое наименьшее число звеньев необходимо разрезать, чтобы путешественник мог платить владельцу отеля одно звено каждое утро, не внося плату заранее?

Первым делом уясним себе, что нет необходимости разрезать все звенья. Если мы разрежем только второе звено, то и первое, и второе будут отделены от остальных пяти звеньев. Следуя этому, можно прийти к решению разрезать только второе, четвертое и шестое звенья цепочки. В результате все звенья окажутся свободными, причем только три из них будут разрезанными (рис. 4.20). Более того, любое меньшее число разрезов оставит два звена соединенными, поэтому мы заключаем, что правильный ответ для этой задачи – три звена.

Однако, рассмотрев задачу более внимательно, можно заметить, что если разрезать только третье звено, то получится три фрагмента цепочки, состоящие из одного, двух и четырех звеньев (рис. 4.21). С этими фрагментами мы можем поступить следующим образом.

Первое утро. Отдать владельцу отеля одно звено.

Второеутро. Забратьувладельцаотеляоднозвеноиотдатьемуфрагментцепочкииздвухзвеньев.

Рис. 4.20. Разделение всех звеньев цепочки с помощью лишь трех разрезов