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

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

1. Основные требования к алгоритмам
1. Каждый алгоритм имеет дело с данными – входными, промежуточными, выходными. Для того, чтобы уточнить понятие данных, фиксируетсяконечный алфавит исходных символов ( цифры, буквы и т.п.) и указываются правила построения алгоритмических объектов. Типичным используемым средством является индуктивное построение. Например, определениеидентификатора в АЛГОЛЕ: идентификатор – это либо буква, либо идентификатор, к которому приписана справа либо буква, либо цифра. Слова конечной длины в конечных алфавитах - наиболее обычный тип алгоритмических данных, ачисло символов в слове - естественная мера объема данных. Другой случай алгоритмических объектов - формулы. Примером могут служить формулы алгебры предикатов и алгебры высказываний. В этом случае некаждое слово в алфавите будет формулой.
2. Алгоритм для размещения данных требует памяти. Память обычно считается однородной и дискретной, т.е. она состоит из одинаковых ячеек, причем каждая ячейкаможет содержать один символ данных, что позволяет согласовать единицы измерения объема данных и памяти.
3. Алгоритм состоит из отдельных элементарных шагов, причем множество различных шагов, изкоторых составлен алгоритм, конечно. Типичный пример множества элементарных шагов – система команд ЭВМ.
4. Последовательность шагов алгоритма детерминирована, т.е. после каждого шага указывается, какой шагследует выполнять дальше, либо указывается, когда следует работу алгоритма считать законченной.
5. Алгоритм должен обладать результативностью, т.е. останавливаться после конечного числа шагов (зависящего от исходных данных ) с выдачей результата. Данное свойство иногда называют сходимостью алгоритма.
6. Алгоритм предполагает наличие механизма реализации, который по описанию алгоритма порождаетпроцесс вычисления на основе исходных данных. Предполагается, что описание алгоритма и механизм его реализации конечны.
Можно заметить аналогию с вычислительными...