Эксперт

Сергей

Задать вопрос

Мы готовы помочь Вам.

Задание

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

Таблица 1.1

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

Рис. 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 до тех пор, пока не получится формула, у которой в правой части отсутствует Т.

Образец выполнения задания 1

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

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

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

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

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

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

Таблица 1.2

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

На следующей итерации: k_{m + 2} = k_{m + 1}  div 2 = 0, что обеспечивает условие завершения цикла. Таким образом, для произвольного n > 0 имеем:

Всего получается m + 2 итераций, где m определяется соотношением . Из последнего соотношения следует:  – ближайшее целое, не превосходящее log₂ n. Итого: количество повторений цикла равняется , а временная сложность группы блоков (6)–(10) составляет O(log n).

Время выполнения конструкции ветвления (блоки (3), (4) и (5)) состоит из времени вычисления логического выражения (блок (3)) и наибольшего из времени, необходимого для выполнения операторов, исполняемых при значении логического выражения true (блок (4)) и при значении false (блок (5)). Каждый из этих блоков имеет время выполнения порядка 0(1), соответственно вся конструкция в целом имеет временную сложность порядка О(1). Группа блоков (1) – (2), так же как и блок (11), имеет время выполнения порядка О(1). Группы блоков (1)–(2), (3)– 5), (6)–(10) и (11) выполняются последовательно. Согласно правилу сумм, общая временная сложность алгоритма T(n) = О(max(1,1,log n,1)) = О(log n).

Следует отметить, что в этом алгоритме имеет место ситуация: T(n) = W (log n), и, следовательно, T(n) = Q (log n).

Вывод. В лабораторной работе проведен анализ алгоритма быстрого возведения в степень. Его временная сложность имеет верхнюю оценку О(log n). Нижняя оценка составляет W (log n), следовательно, имеет место оценка Q (log n).