1.3. Классы входных данных

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

Пример 1.3. Найти максимальный элемент в списке А из N элементов.

Max(A, N)

maxa[1]

for i=2 to N do

If max<a[i]

then maxa[i]

endif

endfor

end

Очевидно, что если список упорядочен в порядке убывания, то перед началом цикла будет сделано 1 присваивание, а в теле цикла – присваиваний не будет. Если список упорядочен по возрастанию, то всего будет сделано N присваиваний (одно – до цикла, и (N-1) – в цикле).

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

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

Пусть, например, наш список состоит из 10 чисел. Число различных расстановок 10 чисел в списке равно 10!=3 628 800.

Применим к списку из 10 чисел вышеприведенный алгоритм поиска максимального элемента. Имеется 362 880 входных множеств, у которых первое число является наибольшим; их все можно поместить в первый класс (1 присваивание и 9 сравнений).

Если наибольшее по величине число стоит на втором месте, то алгоритм сделает 2 присваивания и 9 сравнений. Таких множеств тоже 362 880. Их можно отнести к другому классу.

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

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

Не стоит ограничиваться анализом поведения алгоритма на одном входном наборе данных. Необходимо попытаться найти такие данные, которые обеспечивали бы самое быстрое и самое медленное выполнение алгоритма.

Следовательно, необходимо оценивать среднюю трудоемкость алгоритма на всех возможных наборах данных.

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

Пусть D_А – множество конкретных проблем данной задачи, заданное в формальной системе. Пусть D  D_А – задание конкретной проблемы и |D| = N.

В общем случае существует собственное подмножество множества D_А, включающее все конкретные проблемы, имеющие мощность N:

обозначим это подмножество через D_N : D_N = {D D_N,: |D| = N};

обозначим мощность множества D_N через M_DN → M_DN = |D_N |.

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

1. f_А ^(N) – худший случай – наибольшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

DD_N

f_А ^(N) = max { f_А (D)} – худший случай на D_N..

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

Например, для алгоритма последовательного поиска худший случай состоит в том, что или список с искомой информацией на послед­нем месте, или вообще ее нет.

2. f_А ^(N) – лучший случай – наименьшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

F

DD_N

_a^(N) = min { f_А (D)} – лучший случай на D_N.

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

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

3. f_А (N) – средний случай – среднее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:



DD_N

f_А (N) = (1 / M_DN)* { f_А (D)} – средний случай на D_N

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

Среднее количество операций в этом случае определяется по формуле

 f_А (N) = , где

N – размер входных данных;

m – число групп;

p_i – вероятность того, что входные данные принадлежат группе i;

t_i - количество операций алгоритма («время») для обработки данных из группы с номером i.

В некоторых случаях мы будем предполагать, что вероятности попадания входных данных в каждую из групп одинаковы (1/m).

Упрощенная формула среднего случая

 f_А (N)= .

Вернемся к задаче поиска максимального значения из 3-х чисел (пример 1.1), и определим оценки трудоемкости алгоритма для различных классов входных данных.

MaxABC1(a,b,c) max  a if b>max then maxb endif if c>max then maxc endif return (max) end

MaxABC2(a,b,c) if a>b then if a>c then maxa else maxc endif else if b>c then maxb else maxc endif endif return (max) end

Для алгоритма MaxABC1 в худшем случае, если c>b>a, получаем f_А1 ^=5 (2 сравнения и 3 присваивания). В лучшем случае, если значение (a) является максимумом, имеем: f_А1^=3 (2 сравнения и 1 присваивание). В среднем случае количество выполняемых действий будет равно:

 f_А1^-=P₁* f(1,2,3)+P₂*f(1,3,2)+P₃*f(2,1,3)+P₄*f(2,3,1)+P₅*f(3,1,2)+P₆*f(3,2,1).

Очевидно, что если исходные значения приходят случайным образом, то вероятности P_i появления комбинаций (1,2,3),(1,3,2),(2,1,3),(2,3,1) (3,1,2),(3,2,1) будут равны между собой, то есть P_i = .Тогда получаем

 f_{А 1=}(5+4+4+4+3+3)=3.

Для алгоритма MaxABC2 функция трудоёмкости не зависит от тройки полученных чисел, и всегда будет одинакова: f_{А 2}^= f_{А 2}^=f_{А 2}=3. Этот алгоритм является глобально эффективным.