问求解T（n）= 9T（n / 10）+ log ^ 3 n？

EN

有时用于解决这类复发的技术是通过两次更简单的复发来重复上限和下限，并查看您找到的内容。

例如，请注意您的重复发生

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 log 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）。

总结一下：

• 如果您添加了一个不常见的函数术语，您有时可以通过使用更简单的附加项重复出现的上限和下限来解决该重现。
• 对数由常数下限，并由任何（正，恒定功率）多项式上限。

希望这可以帮助！

使用master方法来解决问题

它解决了形式T（n）= aT（n / b）+ f（n）的重现。

Master Method是获得解决方案的直接方式。主方法仅适用于以下类型的重复或可转换为后续类型的重复。

T（n）= aT（n / b）+ f（n）其中a> = 1且b> 1有以下三种情况：1。如果f（n）=Θ（nc）其中c <Logba则为T（ n）=Θ（nLogba）

1. 如果f（n）=Θ（nc）其中c = Logba则T（n）=Θ（ncLog n）

3.如果f（n）=Θ（nc）其中c> Logba则T（n）=Θ（f（n））

.it用于解决函数的复发，如T（n）= aT（n / b）+ f（n）其中a> = 1且b> 1与您的相同