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

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ[pic 1]

федеральное государственное бюджетное образовательное учреждениевысшего образования

«Тольяттинский государственный университет»

Институт математики, физики и информационных технологий

ПРАКТИЧЕСКОЕ ЗАДАНИЕ №__1_

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

(наименование учебного курса)

Вариант ____ (при наличии)

Тольятти 2023

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

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

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

Задание

Цель работы: получить практические навыки анализа сложности алгоритмов.

1. Задание. Провести анализ и оценку временной сложности алгоритма быстрого возведения в степень (рис. 1.6).

2. Анализ алгоритма. Степень, в которую возводится число, может служить мерой объема входных данных, и все операторы присваивания и сравнения имеют некоторое постоянное время выполнения, независящее от размера входных данных.

[pic 2]

Рис. 1. Блок-схема алгоритма

Наибольшее влияние на временную сложность алгоритма оказывают циклические конструкции. Группа блоков (6)–(10) алгоритма представляет собой цикл с постусловием. Тело цикла (блоки (6)–(9)) имеет временную сложность порядка О(1). Кроме этого, в цикле выполняется проверка условия завершения цикла (блок (10)), которая также имеет время выполнения порядка О(1).

Определим количество повторений тела цикла в зависимости от n. Табл. 1.2 содержит динамику изменения параметра цикла k в зависимости от номера итерации и параметра n.

Анализируя данные, приведенные в табл. 1.2, можно отметить, что на 1-й итерации k1 = n div 20 = n, на этой и каждой последующей итерации k уменьшается в два раза по сравнению с предыдущем значением до тех пор, пока k не станет равно 1 (пусть это будет итерация m+1).

Таблица 1.2

Изменение параметра цикла