我如何解决递归 T(n) = 5T(n/7) + logn？
How can i solve the recursion T(n) = 5T(n/7) + logn?
我正在尝试求解递归 T(n) = 5*T(n/7) + log(n) , T(1) = Theta(1)
我尝试使用递归树方法，但我在寻找树的高度时遇到了困难，而且我不知道如何在这里应用主定理，因为我有 log(n)。谢谢你的时间。
你在这里问了两个问题：
递归树的深度是多少？
你如何使用大定理求解递归关系？
对于问题 (1)，如果您正在尝试调整递归树的大小，这有助于观察在递归运行时输入的大小发生了什么变化。例如，在零递归展开之后，我们有 T(n)。经过一次递归展开后，我们有
T(n) = 5T(n / 7) + log n,
注意T的参数是n/7。经过两次递归展开，我们得到
T(n) = 25T(n / 49) + 5 log (n / 7) + log n,
其中 T 的参数现在是 n / 49。经过第三次递归扩展后，我们得到
T(n) = 125T(n / 343) + 25 log(n / 49) + 5 log (n / 7) + log n,
T 的参数现在是 n / 343。
一个值得思考的好问题：如果你在这个循环中深入 i 次迭代，那么 T 的参数是什么？并且假设当参数为 1 时递归停止，如何求解递归终止处的 i 值？
关于你的第二个问题 - 你在这里如何使用主定理？ - 由于对数项的原因，将主定理直接应用于此问题有点棘手。当您希望使对数项消失时，可以使用的一种有用技术是将重复项夹在其他两个更简单的重复项之间。例如，注意 T(n) 夹在这两个递归之间：
L(n) = 5L(n / 7) + n0
U(n) = 5L(n / 7) + nε, for any ε > 0.
这些递推更直接地符合主定理，如果你很聪明地选择了 ε（提示：让它非常非常小！），你可以证明 L(n) 和 U( n) 都给出相同的渐近界限。由于 T(n) 夹在两者之间，这意味着 T(n) 也将具有相同的渐近增长，您将得到答案。
希望对您有所帮助！
我正在尝试求解递归 T(n) = 5*T(n/7) + log(n) , T(1) = Theta(1)
我尝试使用递归树方法，但我在寻找树的高度时遇到了困难，而且我不知道如何在这里应用主定理，因为我有 log(n)。谢谢你的时间。
你在这里问了两个问题：
递归树的深度是多少？
你如何使用大定理求解递归关系？
对于问题 (1)，如果您正在尝试调整递归树的大小，这有助于观察在递归运行时输入的大小发生了什么变化。例如，在零递归展开之后，我们有 T(n)。经过一次递归展开后，我们有
T(n) = 5T(n / 7) + log n,
注意T的参数是n/7。经过两次递归展开，我们得到
T(n) = 25T(n / 49) + 5 log (n / 7) + log n,
其中 T 的参数现在是 n / 49。经过第三次递归扩展后，我们得到
T(n) = 125T(n / 343) + 25 log(n / 49) + 5 log (n / 7) + log n,
T 的参数现在是 n / 343。
一个值得思考的好问题：如果你在这个循环中深入 i 次迭代，那么 T 的参数是什么？并且假设当参数为 1 时递归停止，如何求解递归终止处的 i 值？
关于你的第二个问题 - 你在这里如何使用主定理？ - 由于对数项的原因，将主定理直接应用于此问题有点棘手。当您希望使对数项消失时，可以使用的一种有用技术是将重复项夹在其他两个更简单的重复项之间。例如，注意 T(n) 夹在这两个递归之间：
L(n) = 5L(n / 7) + n0
U(n) = 5L(n / 7) + nε, for any ε > 0.
这些递推更直接地符合主定理，如果你很聪明地选择了 ε（提示：让它非常非常小！），你可以证明 L(n) 和 U( n) 都给出相同的渐近界限。由于 T(n) 夹在两者之间，这意味着 T(n) 也将具有相同的渐近增长，您将得到答案。
希望对您有所帮助！