Выводы из анализа сложности алгоритма.

Как правило, около 90% времени работы программы требует выполнение повторений (циклов) и только 10% составляют непосредственно вычисления. Анализ сложности программ показывает, на какие фрагменты выпадают эти 90% -это циклы наибольшей глубины вложенности. Повторения могут быть организованы в виде вложенных циклов или вложенной рекурсии.

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

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

Затем следует рассмотреть возможность сокращения количества операторов в циклах с наибольшей глубиной вложенности. Если 90% времени выполнения составляет выполнение внутренних циклов, то 30%-ное сокращение этих небольших секций приводит к 90%*30%=27%-му снижению времени выполнения всей программы.

Упражнения.

1.Дано целое число а и натуральное (целое неотрицательное) число n. Вычислить а в степени n. Произвести анализ сложности алгоритма.

2. Решить предыдущую задачу, если требуется, чтобы сложность алгоритма была порядка log n (log n - это степень, в которую нужно возвести 2, чтобы получить n).

 

3.Дано натуральное n, вычислить 1/0!+1/1!+...+1/n!. Оценить сложность алгоритма.

 

4. То же, если требуется, чтобы сложность алгоритма была О(n) , т.е. количество операций (выполненных команд присваивания) было бы не более C*n для не которой константы С.

 

5. Составить программу, печатающую квадраты всех натуральных чисел от 0 до заданного натурального n. Оценить сложность алгоритма.

 

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