Классы входных сигналов.

 

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

 

 

Например, ищем наибольший элемент в списке из N элементов.:

 

 

largest=list[1]

for i=2 tо N do

if(list[i]>largest) then

largest=list[i]

end if

end for

 

Какие могут быть варианты?

 

1) Список упорядочен в порядке убывания. Тогда перед началом цикла будет сделано одно присваивание, а в теле цикла присваиваний не будет.

 

2) Ну а если список упорядочен по возрастанию? Тогда будет сделано N присваиваний (одно перед началом цикла и N-1 в цикле. Если мы проводим анализ, то не должны ограничиваться одним множеством, вдруг окажется, что это самое быстрое, или наоборот самое медленное множество? Мы должны рассматривать все возможные типы множеств. Для этого разбивают различные входные множества на классы. В зависимости от поведения алгоритма на каждом множестве.

 

 

Пример. Число различных перестановок 10 различных чисел в списке 10!=3 628 800. А мы хотим найти наибольший элемент. У нас есть 362880 входных множеств, у которых первое число является наибольшим. Их все можно поместить в один класс.

Если наибольшее число стоит на 2 месте, то алгоритм сделает ровно 2 присваивания. Множеств, в которых наибольшее число стоит на втором месте, 362880. Их можно отнести к другому классу. Мы видим, как будет меняться число присваиваний при изменении положения наибольшего числа от 1 до N. А это значит, что мы должны разбить все входные множества на N различных классов по числу сделанных присваиваний. Нет необходимости выписывать или описывать детально все множества, помещенные в каждый класс. Надо знать лишь количество классов и объем работы на каждом множестве класса.

 

Число возможных наборов входных данных может стать очень большим при увеличении N. 10 разных чисел можно расположить в списке 3628800 способами. Все эти способы рассмотреть невозможно. Но мы разбили списки на классы в зависимости от того, что будет делать алгоритм. У нашего алгоритма разбиение основывается на местоположении наибольшего значения. В результате получили 10 разных классов.

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

 

 

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

 

Наилучший случай.

 

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

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

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

 

Наихудший случай.

 

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

 

Средний случай

 

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

 

A(n)= ,

 

где через n обозначен размер входных данных, через m- число групп, через p- вероятность того, что входные данные принадлежат группе с номером i, а через t – время, необходимое алгоритму для обработки данных из группы с номером i.

В некоторых случаях мы будем предполагать, что вероятность попадания входных данных в каждую из групп одинакова. ( Если, например, групп 5, то вероятность попасть в первую группу такая же как вероятность попасть во 2 и т. д., то есть вероятность попасть в каждую группу 0.2.

Тогда можно воспользоваться упрощенной формулой

 

A(n)=