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

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

Модуль 1. Математические модели проектирования программного обеспечения

Лекция 1.1. Математические модели алгоритмов программного обеспечения

Задание

Провести анализ и оценку временной сложности заданного алгоритма. Варианты заданий представлены в таблице (выбор варианта задания осуществляется по первой букве фамилии). Блок схемы алгоритмов – на рис. 1.1–1.6. В блок-схемах символ div обозначает операцию целочисленного деления, mod – остаток от целочисленного деления.

Таблица 1.1

Варианты заданий

Ч, Ш, Щ, Э, Ю, Я

6

Алгоритм вычисления значения многочлена по схеме Горнера (рис. 1.4)

Рис. 1.1. Тривиальный алгоритм возведения x в степень n

Рис. 1.2. Рекурсивный алгоритм возведения x в степень n

а)                                                    б)

Рис. 1.3. Алгоритмы быстрого возведения x в степень n

Рис.1.4. Алгоритм вычисления значения многочлена степени n, заданного массивом своих коэффициентов A = {A[0], A[1], …, A[n]} при некотором значении переменной x по схеме Горнера

Рис. 1.5. Алгоритм вычисления значения многочлена степени n, заданного массивом своих коэффициентов A = {A[0], A[1], …, A[n]} при некотором значении переменной x

Рекомендации по выполнению задания

Практическое определение времени выполнения основано на следующих правилах. 

1.    За функцию берется количество операций, возрастающее быстрее всего.

2.    Константы не учитываются, в том числе и основания логарифма. 

3.    Для времени выполнения программы в целом допустимым параметром может быть только n, размер входных данных.

4.    Время выполнения операторов присваивания обычно имеет порядок О(1).

5.    Время выполнения операторов ввода – вывода обычно имеет порядок О(1).

6.    Время выполнения последовательности операторов определяется суммированием.

7.    Время выполнения цикла является суммой времени всех исполняемых итераций цикла. Время выполнения каждого цикла, если в программе их несколько, должно определяться отдельно.

8.     Для программ, содержащих несколько процедур или функций, общее время выполнения программы равно сумме времен выполнения подпрограмм.

9.    В случае когда имеют место рекурсивные процедуры или функции, необходимо с каждой рекурсивной процедурой (функцией) связать временною функцию Т(n), где n определяет объем ее аргументов, и получить рекуррентное соотношение для T(n), представляющее собой уравнение (или неравенство) для Т(п), где участвуют значения T(k) для различных значений k < n. Решение таких рекуррентных соотношений состоит в последовательном раскрытии выражений Т(к) в правой части уравнения путем подстановки в исходное соотношение k вместо n до тех пор, пока не получится формула, у которой в правой части отсутствует Т.