求解递归 T(n) = T(n/5) + T(7n/10) + Θ(n)
Solving recurrence T(n) = T(n/5) + T(7n/10) + Θ(n)
我想以 Θ 的精度解决这个递归问题：
T(n) = T(n/5) + T(7n/10) + Θ(n)
我可以解决典型的递归问题，但我不知道如何处理这个问题，因为它与主定理的任何情况都不匹配。
任何帮助或提示？
您可以使用主定理的 Akra-Bazzi 概括。
如果 Theta(n) 项被替换为更小的值，例如在这种情况下的 Theta(1) 或 Theta(sqrt(n))，您可以简单地找到 alpha 的值，以便 n^alpha = ( n/5)^alpha + (7n/10)^alpha 通过分解 n^alpha。但是，如果这样做，您会得到 alpha = 0.84，并且 n^0.84 渐近地小于 Theta(n)，因此如果您迭代递归直到参数变小，则 Theta(n) 项的贡献将占主导地位。结果是 T(n) 是 Theta(n)，尽管其常数与递归中的 Theta(n) 不同。
我想以 Θ 的精度解决这个递归问题： T(n) = T(n/5) + T(7n/10) + Θ(n)
我可以解决典型的递归问题，但我不知道如何处理这个问题，因为它与主定理的任何情况都不匹配。
任何帮助或提示？
您可以使用主定理的 Akra-Bazzi 概括。
如果 Theta(n) 项被替换为更小的值，例如在这种情况下的 Theta(1) 或 Theta(sqrt(n))，您可以简单地找到 alpha 的值，以便 n^alpha = ( n/5)^alpha + (7n/10)^alpha 通过分解 n^alpha。但是，如果这样做，您会得到 alpha = 0.84，并且 n^0.84 渐近地小于 Theta(n)，因此如果您迭代递归直到参数变小，则 Theta(n) 项的贡献将占主导地位。结果是 T(n) 是 Theta(n)，尽管其常数与递归中的 Theta(n) 不同。