#math #time-complexity #recurrence
#математика #временная сложность #повторение
Вопрос:
Меня попросили найти асимптотическую сложность данной функции, используя дерево рекурсии, но я изо всех сил пытаюсь найти правильную сложность на каждом уровне
Ответ №1:
Давайте нарисуем первые два уровня дерева рекурсии:
------------------
| Input size n |
| Work done: n^2 |
------------------
/
-------------------- --------------------
| Input size: 3n/4 | | Input size: n/3 |
| Work done: 9n^2/16 | | Work done: n^2/9 |
-------------------- --------------------
Как только мы это сделаем, давайте подведем итоги работы, проделанной каждым слоем. Этот верхний слой выполняет n 2 работы. Этот следующий слой выполняет
(9/16)n2 (1/9)n2 = (43/48)n2
общая работа. Обратите внимание, что работа, проделанная на этом втором уровне, составляет (43/48) тыс. работы, проделанной на уровне чуть выше него. Если вы расширите еще несколько уровней дерева рекурсии, вы обнаружите, что следующий уровень выполняет (43/48) 2 n 2 работы, уровень ниже, который выполняет (43/48) 3 n 2 работы, и что в более общем случае работа, выполняемая уровнем l в дереве, равна (43/48) ln 2. (Убедите себя в этом — не просто верьте мне на слово!)
Оттуда вы можете вычислить общий объем работы, проделанной деревом рекурсии, путем суммирования работы, проделанной за уровень на всех уровнях дерева. В качестве подсказки вы смотрите на сумму геометрической последовательности, которая распадается от одного члена к следующему — напоминает ли это вам какой-либо из случаев Основной теоремы?