求解 T(n) = 9T(n / 10) + log^3 n？

Question

我有复发

T(n) = 9T(n/10) + log³ n

我正在尝试找出它的复杂性。

i-替换后我可以看到

T(i) = 9T(n / 10ⁱ⁺¹) + log³(n / 10ⁱ).

但是我不知道如何继续。我该如何解决这个问题？

Answer 1

用大师方法解决问题

它求解形式 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)

2. 如果 f(n) = Θ(nc) 其中 c = Logba 则 T(n) = Θ(ncLog n)

3.If f(n) = Θ(nc) 其中 c > Logba 然后 T(n) = Θ(f(n))

.它用于解决函数中的递归问题，例如 T(n) = aT(n/b) + f(n) 其中 a >= 1 且 b > 1 和你的一样

Answer 2

一种有时对解决此类递归有用的技术是用两个更简单的递归来计算上层递归和 lower-bound 递归，然后看看你找到了什么。

例如，请注意您的复发

T(n) = 9T(n / 10) + log³ n

lower-bound由重复

编辑

L(n) = 9L(n / 10) + 1.

这个递推可以直接用主定理求解。 Master Theorem 有许多不同的公式，但我最喜欢的是解决形式

的递归公式

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).

同样，请注意您的重复率是 upper-bounded by

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), 所以你的递归求解为 Θ(n^log₁₀9).

总结：

• 如果您有一个添加了不寻常函数项的递归，有时您可以通过上层和 lower-bound 使用具有更简单的附加项的递归来解决该递归。

• 对数由常数 lower-bound 和任何（正数，constant-power）多项式 upper-bounded 计算。

希望对您有所帮助！