Решение T (n) = 9T (n / 10) + log ^ 3 n?

использовать мастер-метод для решения проблемы

Он решает повторения вида T(n) = aT(n/b) + f(n).

Мастер-метод — это прямой путь к решению. Мастер-метод работает только для повторений следующего типа или для повторений, которые могут быть преобразованы в следующий тип.

T(n) = aT(n/b) + f(n), где a >= 1 и b > 1 Возможны следующие три случая: 1. Если f(n) = Θ(nc), где c < Logba, то T(n) = Θ(nLogba)

2. Если f(n) = Θ(nc), где c = Logba, то T(n) = Θ(ncLog n)

3. Если f(n) = Θ(nc), где c > Logba, то T(n) = Θ(f(n))

.он используется для решения повторений в таких функциях, как T(n) = aT(n/b) + f(n), где a >= 1 и b > 1 такой же как твой

Техника, которая иногда полезна для решения подобных повторений, состоит в том, чтобы оценить повторение как сверху, так и снизу с двумя более простыми повторениями и посмотреть, что вы найдете.

Например, обратите внимание, что ваш повтор

T(n) = 9T(n / 10) + log³ 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^log₁₀9). Это означает, что мы знаем, что ваша повторяемость не меньше Ω(n^log₁₀9).

Точно так же обратите внимание, что ваше повторение ограничено сверху

U(n) = 9U(n / 10) + n^ε

для любого фиксированного ε > 0, поскольку любой полиномиальный член доминирует над любой постоянной степенью логарифмического члена. Давайте представим, что ε очень и очень мало. Что в этом случае говорит Основная теорема? Здесь мы имеем a = 9, b = 10 и d = ε. Предполагая, что ε действительно очень, очень мало, мы получим, что log_b a > ε, и поэтому рекуррентность сводится к Θ(n^log₁₀9).

Это показывает, что ваше повторение хорошо зажато между двумя другими повторениями, которые равны Ω(n^log₁₀9) и O(n^log₁₀9) соответственно, поэтому ваше повторение решается как Θ (п^log₁₀9).

Обобщить:

• Если у вас есть повторение с добавленным необычным функциональным термином, вы иногда можете решить это повторение, ограничив его сверху и снизу повторениями с более простыми аддитивными членами.

• Логарифмы ограничены снизу константами и сверху любым полиномом (положительным, постоянной степени).

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