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

Пространство или время

Чем больше мы изучаем, разрабатываем и анализируем алгоритмы, тем чаще мы сталкиваемся с одним универсальным законом вычислительной техники: быстрые алгоритмы, как правило, требуют больше памяти. Таким образом, для использования быстрого алгоритма необходимо располагать большим объемом памяти.

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

Листинг 1.3. Первоначальная функция определения количества установленных битов в байте

function CountBitsl(B : byte):byte;

begin

Result := 0;

while (B <> 0) do

begin

if Odd(B) then

inc(Result);

B := B shr 1;

end;

end;

Как видите, в этой функции не используются промежуточные переменные. Она просто считает установленные биты путем деления значения на 2 (сдвиг целого значения на один бит вправо эквивалентно делению на 2) и определения количества полученных нечетных результатов. Цикл завершается, когда будет получено значение 0, поскольку в этом случае очевидно, что установленных битов больше нет. Значение О большого для приведенного алгоритма зависит от количества установленных битов в параметре, и в худшем случае внутренний цикл будет выполнен восемь раз. Таким образом, это алгоритм класса O(n).

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

Тем не менее, давайте рассмотрим назначение алгоритма с другой точки зрения. В качестве входного значения функция принимает 1-байтный параметр, с помощью которого можно передать всего 256 значений. В таком случае, почему бы нам заранее не вычислить все возможные ответы и не записать их в статический массив? Реализация нового алгоритма приведена в листинге 1.4.

Листинг 1.4. Улучшенная функция определения количества установленных битов в байте const

BitCounts : array [0..255] of byte =

(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,