(Оценка времени работы алгоритмов)

Оценка времени работы алгоритмов

Цель работы:

-Научиться оценивать сложность алгоритма по псевдокоду или блок-схеме;

-Научиться находить (оценивать) решение рекуррентного соотношения методом подстановок (см. пример из в презентации);

-Научиться определять порядок роста решения рекуррентного соотношения, к которому приводит анализ вычислительной сложности рекурсивных алгоритмов определённого класса (см. лекцию 2, слайды 34-35) по практическим правилам (слайд 36);

-Находить решение в случае мультипликативной управляющей функции (слайд 37) и оценивать степень роста решения по правилам (слайд 38).

В задачах 2-3 надо найти и оценить скорость роста решения (только оценить решение в случае невозможности вычисления суммы).

В задаче 4 надо применить выведенные в лекции формулы и получить решение и его скорость роста или только оценить решение в случае невозможности вычисления суммы.

Суммы, которые надо обязательно считать: арифметическая и геометрическая прогрессия, сумма из примера на слайдах 10-11 презентации с примерами решения задач ЛР №2.

Решить необходимо только один вариант!