о алгоритму на задачах розміру. Решта обчислення можна виконати за час, оскільки вони містять один з аргументів або єдиний біт або, або ступінь числа 2 .
Таким чином, число використовуваних операцій обмежена зверху
В
де - постійна, що відображає число складань і зрушень в алгоритмі. Доведемо по індукції, що звідси випливає формула. Очевидно, що при початкові умови виконані. Нехай для формула є рішення рекурсивного співвідношення. Тоді маємо (тут використано рівність) .). Таким чином явна формула справедлива для. Затвердження доведено. p> Ясно, що і даний алгоритм краще по порядку вихідного В«НаївногоВ» алгоритму. Зауважимо, що для даної задачі відомі і більш кращі алгоритми [12].
2. Множення матриць. Дано дві квадратні матриці порядку з елементами з деякого кільця і ​​потрібно знайти їх твір. Стандартний алгоритм вимагає множень і складань елементів К. На перший погляд, здається, що неможливо скільки-небудь істотно зменшити дане число операцій, Однак, В. Штрассені [13] був запропонований наступний алгоритм.
Нехай. Тоді твір матриць знаходиться одним множенням.
Нехай і дано матриці,. Покладемо. Тоді матриця може бути обчислена так. Нехай,,,,,,. Тоді знаходимо,,,. p> Зауважимо, в даному алгоритмі використано 7 множень і 18 складань і не використана коммутативность множення.
Нехай тепер. Тоді алгоритм множення матриць працює так: матриці іВ порядку представляються як-матриці над кільцем матриць порядку і застосовується викладений вище алгоритм множення-матриць. Якщо ж, то перебуває таке , що і до матриць додається потрібне число нульових рядків і стовпців.
Нехай - число арифметичних операцій, використовуваних в алгоритмі на матрицях розміру. Тоді справедливі співвідношення: і. Враховуючи ці умови, доведемо формулуВ . При і формула справедлива. Нехай для формула дійсно випливає з співвідношень. Маємо при: тобто наша формула справедлива і для. Затвердження доведено. Ясно, що виконується. Значить, представлений алгоритм краще по порядку вихідного алгоритму (зауважимо, що).
Розглянемо тепер у загальному вигляді питання про складність алгоритмів, що використовують рекурсію. З наведених вище прикладів, ясно, що складність рекурсивних алгоритмів виражається рекурентними співвідношеннями. Якщо в рекурсивному алгоритмі використовується одна процедура, то значення складності для завдання розміру визначається значеннями для аргументів, де. Однак виникаючі при цьому рекурентні співвідношення вирішуються в кінцевому вигляді в дуже рідкісних випадках. При рівномірному розбитті завдання розміру розбивається на підзадач розміру, де - деяка фіксована константа в рекурсивному алгоритмі, при цьому функція складності визначається рекурентним співвідношенням виду:
В
де - константа,, - невід'ємні, цілочисельні, монотонні функції, що характеризують складність отримання рішення вихідної задачі розміру зВ рішень під...
