Техника, которая иногда полезна для решения подобных повторений, состоит в том, чтобы и верхнюю, и нижнюю границу повторения с двумя более простыми повторениями и посмотреть, что вы найдете.
Например, обратите внимание, что ваше повторение
T (n) = 9T (n / 10) + log 3 n
ограничено снизу повторением
L (n) = 9L (n / 10) + 1.
Это повторение может быть непосредственно решено с помощью основной теоремы.Существует много различных формулировок основной теоремы, но моя любимая - та, которая решает повторения вида
T (n) = aT (n / b) + n d
для констант a, b и d.В этом случае мы имеем a = 9, b = 10 и d = 0, и, поскольку log b a> d, это означает, что рекуррентность разрешается в L (n) = Θ (n * журнал 1028 * 10 9 ).Это означает, что мы знаем, что ваше повторение составляет не менее Ω (n log 10 9 ).
Аналогично, обратите внимание, что ваше повторение ограничено сверху
U (n) = 9U (n / 10) + n ε
для любого фиксированного ε> 0, так как любой полиномиальный член доминирует над любой постоянной степеньюлогарифмического термина.Давайте представим, что ε очень, очень мало.Что говорит основная теорема в этом случае?Здесь имеем a = 9, b = 10 и d = ε.Предполагая, что ε действительно очень и очень мало, мы будем иметь этот log b a> ε, и поэтому рекуррентность решается как Θ (n log 10 9 ).
Это показывает, что ваше повторение приятно зажато между двумя другими повторениями: Ω (n log 10 9 ) и O (n log 10 9 ) соответственно, поэтому ваше повторение разрешается до Θ (n log 10 9 ) .
Подводя итог:
Если у вас есть рекурсия с добавленным необычным функциональным термином, вы можете иногда решить эту рекурсию, ограничивая ее верхней и нижней границей рекурсиями с более простыми аддитивными терминами.
Логарифмы ограничены снизу константами и ограничены сверху любым (положительным, постоянным) полиномом.
Надеюсь, это поможет!