Как решить рекурсию T(n) = 5T(n/7) + logn?

Я пытаюсь решить рекурсию T(n) = 5*T(n/7) + log(n) , T(1) = Theta(1)

Я попытался использовать метод рекурсивного дерева, но застрял, пытаясь найти высоту дерева, и я не знаю, как применить здесь основную теорему, поскольку у меня есть log (n). Спасибо за уделенное время .

Вам не нужна программа для решения простой рекурсии. Это домашнее задание. Я говорю о нахождении высоты рекурсивного дерева приведенной выше рекурсии.

user9994319 23.06.2019 19:18
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
1
685
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вы задали здесь два вопроса:

  1. Какова глубина дерева рекурсии?

  2. Как решить рекуррентное соотношение с помощью основной теоремы?

Что касается вопроса (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) также будет иметь такой же асимптотический рост, и вы получите свой ответ.

Надеюсь это поможет!

Другие вопросы по теме