задач розміру. Ясно, що дане співвідношення визначає однозначно функцію тільки при значеннях аргументів виду, де. Для практичних додатків являє інтерес виділення випадків, коли рішення обмежена зверху поліномом від.
Легко доводиться, що якщо функція задовольняє умові: існує, таке, що справедливе співвідношення для всіх натуральних, то чи не мажоріруется зверху ніяким поліномом від [14]. Таким чином, в Надалі обмежимося випадком,, де,, - фіксовані цілі числа.
Тепер можна довести, що справедливо наступне твердження [15]. Нехай дано рекурентне співвідношення
В
де,В ,,, - Фіксовані константи. Тоді при, де, рішенням співвідношення є вираз
В
Далі випливає наслідок [16], що в припущеннях попереднього твердження справедливі співвідношення
В
У деяких випадках рекурсію для задачі розміру вдається організувати тільки шляхом адитивного зменшення вихідного розміру задачі на деяку константу. Складність такого типу рекурсивних алгоритмів визначається рекурентним співвідношенням виду
В
де,В ,,, - Фіксовані константи. Наприклад, така ситуація виникає при вирішенні графічних завдань. Для такого співвідношення при, де, справедлива оцінка [17]
В
У деяких випадках для організації рекурсії використовується В«квадратичнеВ» розбиття, при якому вихідна завдання розміру розбивається на підзадач розміру. Для складності рекурсивного алгоритму виникає наступне рекурентне рівняння
В
де,В , - Фіксовані константи. Воно визначає однозначно функцію при таким виразом [18]
В
Дані результати мають практичний інтерес. У Як приклад помітимо, що для задачі сортування можна запропонувати рекурсивні алгоритми, які використовують як розбиття задачі на довільне фіксоване число підзадач, так і квадратичне розбиття. Ці алгоритми дають кращі оцінки, ніж навіть швидке сортування бінарним розбиттям на підзадачі. p> Для задачі множення матриць використання базового алгоритму множення-матриць з множеннями для побудови рекурсивного алгоритму, що зводить множення-матриць до множення-матриць призводить до оцінок для Складність:
В
(в алгоритмі Штрассена,). В. Пан використовував алгоритм з параметрами і й отримав. В даний час відомі і більш кращі алгоритми. Зусиллями ряду математиків (Пан, Виноград, Романі, Шейхаге, Штрассен, Копперсміт) експонента складності матричного множення послідовно приймала значення:,В ,,,,. Основна проблема - знаходження докази рівності ще не вирішена [19].
Розглянемо ще один приклад застосування отриманих результатів. Повернемося до задачі множення чисел у двійковій запису. Зафіксуємо натуральне число і розглянемо два-бітових числа і, де
,
.
Розіб'ємо ці числа на частин
,
.
Тут кожне і, є-бітовими числами,. Розглянемо багаточлени
В В
і утворюємо твір. Ясно, що виконано,,. Тому, знання многочлена дозволяє обчислити добуток за число дій пропорційне. Щоб знайти коефіцієнти многочлена знаходимо...
