Читать «Фундаментальные алгоритмы и структуры данных в Delphi» онлайн - страница 10

В мире программирования мы представляем себе алгоритмы как сложные методы выполнения определенных вычислений. Например, если имеется массив записей покупателей, в котором необходимо найти определенного покупателя (скажем, Джона Смита (John Smith)), то можно действовать следующим образом: считывать каждый элемент массива, пока не будет найдена нужная запись или не будет достигнут конец массива. Для вас это может показаться очевидным методом решения поставленной задачи, тем не менее, в мире алгоритмов он известен как последовательный поиск (sequential search).

Существуют и другие методы поиска элемента "John Smith" в нашем гипотетическом массиве. Например, если элементы в массиве отсортированы по фамилии, то можно воспользоваться алгоритмом бинарного поиска (binary search). Согласно ему, мы берем средний элемент массива. Это "John Smith"? Если да, то поиск закончен. Если элемент меньше чем "John Smith" (под "меньше" здесь понимается, что он стоит "раньше" в алфавитном порядке), то можно сказать, что искомый элемент находится во второй половине массива, если же он больше, то нужный нам элемент находится в первой половине массива. Далее операции повторяются (т.е. мы снова берем средний элемент выбранной части массива, сравниваем его с элементом "John Smith" и выбираем ту часть, в которой этот элемент должен находиться) до тех пор, пока элемент не будет найден, или пока левая часть массива после очередного разбиения не окажется пустой.

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

Что ж, добро пожаловать в мир анализа алгоритмов, в котором мы постоянно проводим эксперименты и пытаемся сформулировать законы работы различных алгоритмов!

Анализ алгоритмов

Рассмотрим два возможных варианта поиска в массиве элемента "John Smith": последовательный поиск и бинарный поиск. Мы напишем код для обоих вариантов, а затем определим производительность каждого из них. Реализация простого алгоритма последовательного поиска приведена в листинге 1.1.

Листинг 1.1. Последовательный поиск имени в массиве элементов

function SeqSearch( aStrs : PStringArray;

aCount : integer; const aName : string5): integer;

var

i : integer;

begin

for i := 0 to pred(aCount) do

if CompareText(aStrs^[i], aName) = 0 then begin

Result := i;

Exit;

end;

Result := -1;

end;

В листинге 1.2 содержится код более сложного бинарного поиска. (пока что мы не будем объяснять, что происходит в этом коде. Алгоритм бинарного поиска подробно рассматривается в главе 4.)