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