Я пытаюсь решить рекурсию T(n) = 5*T(n/7) + log(n) , T(1) = Theta(1)
Я попытался использовать метод рекурсивного дерева, но застрял, пытаясь найти высоту дерева, и я не знаю, как применить здесь основную теорему, поскольку у меня есть log (n). Спасибо за уделенное время .
Вы задали здесь два вопроса:
Какова глубина дерева рекурсии?
Как решить рекуррентное соотношение с помощью основной теоремы?
Что касается вопроса (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.
Хороший вопрос для размышления: если вы углубитесь в это повторение на i итераций, каким будет аргумент T? И учитывая, что рекурсия останавливается, когда аргумент равен 1, как вы можете найти значение i, где рекурсия заканчивается?
На ваш второй вопрос - как вы используете здесь основную теорему? - применить основную теорему непосредственно к этой проблеме немного сложно из-за логарифмического члена. Полезный метод, который вы можете использовать, когда у вас есть термины журнала, которые вы хотите заставить исчезнуть, состоит в том, чтобы поместить повторение между двумя другими, более простыми повторениями. Обратите внимание, например, что T(n) зажато между этими двумя повторениями:
L(n) = 5L(n / 7) + n0
U(n) = 5L(n / 7) + nε, for any ε > 0.
Эти повторения гораздо более прямо вписываются в основную теорему, и если вы сообразительны в выборе ε (подсказка: сделайте его очень, очень маленьким!), вы можете показать, что L(n) и U(n) оба дают та же асимптотическая оценка. Поскольку T(n) зажато между ними двумя, это означает, что T(n) также будет иметь такой же асимптотический рост, и вы получите свой ответ.
Надеюсь это поможет!
Вам не нужна программа для решения простой рекурсии. Это домашнее задание. Я говорю о нахождении высоты рекурсивного дерева приведенной выше рекурсии.