Структуры и алгоритмы обработки данных

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

Цель работы:

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

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

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