Добавлен: 07.11.2023
Просмотров: 146
Скачиваний: 7
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
. Остальные вычисления можно выполнить за время 
, поскольку они содержат один из аргументов либо единственный бит 
или 
, либо степень числа 2.Таким образом, число используемых операций
ограничено сверху
где
- постоянная, отражающая число сложений и сдвигов в алгоритме. Докажем по индукции, что отсюда следует формула 
. Очевидно, что при 
начальные условия выполнены. Пусть для 
формула есть решение рекурсивного соотношения. Тогда имеем 
(здесь использовано равенство 
).).Таким образом явная формула справедлива для 
. Утверждение доказано.Ясно, что
и данный алгоритм лучше по порядку исходного «наивного» алгоритма. Заметим, что для данной задачи известны и более лучшие алгоритмы 1.2. Умножение матриц. Даны две квадратные матрицы порядка
с элементами из некоторого кольца 
и требуется найти их произведение. Стандартный алгоритм требует 
умножений и 
сложений элементов К. На первый взгляд, кажется, что невозможно сколько-нибудь существенно уменьшить данное число операций, Однако, В. Штрассеном 2 был предложен следующий алгоритм.
Пусть
. Тогда произведение матриц находится одним умножением.Пусть
и даны матрицы 
, 
. Положим 
. Тогда матрица 
может быть вычислена так. Пусть 
, 
, 
, 
, 
, 
, 
. Тогда находим 
, 
, 
, 
.Заметим, в данном алгоритме использовано 7 умножений и 18 сложений и не использована коммутативность умножения.
Пусть теперь
. Тогда алгоритм умножения матриц работает так: матрицы 
и 
порядка 
представляются как 
-матрицы над кольцом матриц порядка
и применяется изложенный выше алгоритм умножения 
-матриц. Если же 
, то находится такое 
, что 
и к матрицам добавляется нужное число нулевых строк и столбцов.Пусть
- число арифметических операций, используемых в алгоритме на матрицах размера . Тогда справедливы соотношения: 
и 
. Учитывая эти условия, докажем формулу 
. При 
и 
формула справедлива. Пусть для формула действительно следует из соотношений.Имеем при 
: 
т.е. наша формула справедлива и для . Утверждение доказано. Ясно, что выполняется 
. Значит, представленный алгоритм лучше по порядку исходного алгоритма (заметим, что 
).Рассмотрим теперь в общем виде вопрос о сложности алгоритмов, использующих рекурсию. Из приведенных выше примеров, ясно, что сложность рекурсивных алгоритмов выражается рекуррентными соотношениями. Если в рекурсивном алгоритме используется одна процедура, то значение сложности
для задачи размера
определяется значениями 
для аргументов 
,где 
. Однако возникающие при этом рекуррентные соотношения решаются в конечном виде в очень редких случаях. При равномерном разбиении задача размера разбивается на подзадач размера 
, где - некоторая фиксированная константа в рекурсивном алгоритме, при этом функция сложности 
определяется рекуррентным соотношением вида:
где
- константа, 
, 
- неотрицательные, целочисленные, монотонные функции, характеризующие сложность получения решения исходной задачи размера из решений подзадач размера . Ясно, что данное соотношение определяет однозначно функцию только при значениях аргументов вида 
, где 
. Для практических приложений представляет интерес выделение случаев, когда решение
ограничено сверху полиномом от
.Легко доказывается, что если функция
удовлетворяет условию: существует 
, такое, что справедливо соотношение 
для всех натуральных , то не мажорируется сверху никаким полиномом от 1. Таким образом, в дальнейшем ограничимся случаем 
, 
, где 
, 
, 
- фиксированные целые числа.Теперь можно доказать, что справедливо следующее утверждение 2. Пусть дано рекуррентное соотношение
где
, , 
, , - фиксированные константы. Тогда при 
, где 
, решением соотношения является выражение
Далее вытекает следствие 3, что в предположениях предыдущего утверждения справедливы соотношения
