Вы задали два вопроса здесь:
Какова глубина дерева рекурсии?
Как решить рекуррентное соотношение, используя основную теорему?
В вопросе (1), если вы пытаетесь определить размер дерева рекурсии, полезно наблюдать за тем, что происходит с размером входных данных при выполнении рекурсии. Например, после нуля рекурсивных разложений имеем T (n). После одного рекурсивного расширения мы имеем
T (n) = 5T (n / 7) + log n,
и обратите внимание, что аргументом для T является n / 7. После двух рекурсивных разложений мы получаем
T (n) = 25T (n / 49) + 5 log (n / 7) + log n,
где аргумент для T теперь n / 49. После третьего рекурсивного раскрытия мы получаем
T (n) = 125T (n / 343) + 25 log (n / 49) + 5 log (n / 7) + log n,
и аргумент для T теперь n / 343.
Хороший вопрос для размышления: если вы итерируете глубоко в этом повторении, каким будет аргумент для T? И учитывая, что повторение останавливается, когда аргумент равен 1, как вы можете определить для значения i, где рекурсия заканчивается?
На ваш второй вопрос - как вы здесь используете основную теорему? - применение основной теоремы непосредственно к этой проблеме немного сложно из-за логарифмического термина. Полезная техника, которую вы можете использовать, когда у вас есть термины журнала, которые вы хотите сделать исчезающими, - это сэндвич с повторением двух других, более простых повторений. Обратите внимание, например, что T (n) находится между этими двумя повторениями:
L (n) = 5L (n / 7) + n 0
U (n) = 5L (n / 7) + n & epsilon; , для любого & epsilon; > 0.
Эти повторения гораздо более непосредственно вписываются в основную теорему, и если вы сообразительны к тому, как вы выбираете & epsilon; (подсказка: сделайте это действительно очень маленьким!), вы можете показать, что L (n) и U (n) дают одинаковую асимптотическую оценку. Поскольку T (n) находится между двумя из них, это означает, что T (n) также будет иметь такой же асимптотический рост, и у вас будет свой ответ.
Надеюсь, это поможет!