Экспериментальное определение временной сложности детерминистического алгоритма
Автор: user27 • Май 16, 2023 • Практическая работа • 319 Слов (2 Страниц) • 119 Просмотры
ИНОБРНАУКИ РОССИИ
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ
ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
«ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА)
Кафедра алгоритмической математики
ОТЧЕТ
по практической работе № 1
по дисциплине «Компьютерная математика»
Тема: Экспериментальное определение временной сложности детерминистического алгоритма
Студенты гр. | ||
Преподаватель |
Санкт-Петербург
2022
Цель работы.
Целью работы является приобретение знаний, умений, навыков оценивания временной сложности заданного детерминистического алгоритма.
Алгоритм.
Тема №1 – Алгоритм вычисления остатка от произведения чисел (умножение использовать запрещено).
Вход: ;[pic 1]
Выход: - остаток от .[pic 2][pic 3]
1. Формализация вычисляемой величины
Пусть – натуральное число, – двоичная запись этого числа, тогда:[pic 4][pic 5]
,
где , , , .[pic 6][pic 7][pic 8][pic 9][pic 10][pic 11]
– побитовый сдвиг вправо;[pic 12]
– побитовый сдвиг влево;[pic 13]
, где – остаток[pic 14][pic 15]
2. Свойства вычисляемой величины
Пусть тогда остаток от деления на равен , а остаток от деления на равен , тогда:[pic 16][pic 17][pic 18][pic 19][pic 20][pic 21][pic 22]
1) Остаток от деления на равен остатку от деления на соответственно;[pic 23][pic 24][pic 25][pic 26]
;[pic 27]
Предположение: если - вход, то [pic 28][pic 29]
[pic 30]
Чтобы количество умножений было наименьшим, нужно задать следующее условие:
;[pic 31]
3. Рекурсивная формула
;[pic 32]
;[pic 33][pic 34]
[pic 35]
4. Рекуррентная формула
[pic 36]
;[pic 37]
[pic 38]
[pic 39]
;[pic 40]
[pic 41]
Оценка теоретической сложности
n – количество бит чисел а и b
Пусть - сложность выполнения операции * в полукольце [pic 42][pic 43]
...