如何使用递归求解 T(n) = 5T(n/2) + O(nlogn)
How to solve T(n) = 5T(n/2) + O(nlogn) using recursion
所以这可能很愚蠢，但我坚持使用这种递归 T(n) = 5T(n/2) + O(nlogn)。我从 Master Theorem 知道它应该是
，但我真的到不了那里。
到目前为止我达到了
我只是想知道我的方向是否正确
您绝对是在正确的轨道上！让我们看看是否可以简化该求和。
首先，请注意您可以从求和中提取 log n 项，因为它独立于求和。这给了我们
(n log n) (sum from k = 0 to lg n (5/2)k)
那个和是一个几何级数的和，所以它解为
((5/2)log n + 1 - 1) / (5/2 - 1)
= O((5/2)lg n)
在这里，我们可以使用（可爱的）恒等式 alogb c = clogb a 重写
O((5/2)lg n) = O(nlg 5/2)
= O(nlg 5 - 1)
将其代入我们的原始公式可以得到
n log n · O(nlg 5 - 1) = O(nlg 5 log n).
嗯，这不太奏效。不过，我们真的非常接近在这里工作的东西！一个很好的问题是 为什么 这不起作用，为此，我们必须首先回到您如何获得原始求和的问题。
让我们尝试使用递归方法展开递归T(n) 的一些项。第一次扩展给我们
T(n) = 5T(n / 2) + n log n.
下一个是有趣的地方：
T(n) = 5T(n / 2) + n log n
= 5(5T(n / 4) + (n / 2) log (n / 2)) + n log n
= 25T(n / 4) + (5/2) log (n / 2) + n log n
然后我们得到
T(n) = 25T(n / 4) + (5/2) log (n/2) + n log n
= 25(5T(n / 8) + (n / 4) log (n / 4)) + (5/2) log (n/2) + n log n
= 125T(n / 8) + (25/4)n log (n / 4) + (5/2) log (n/2) + n log n
这里的一般模式似乎是以下总和：
T(n) = sum from i = 0 to lg n (5/2)kn lg(n/2k)
= n sum from i = 0 to lg n (5/2)k lg(n/2k)
请注意，这不是您的原始总和！特别要注意的是，对数项不是 log n，而是一个增长速度比它慢得多的函数。事实上，随着 k 变大，对数项变得非常非常小。事实上，如果您考虑一下，我们唯一一次真正支付全部 lg n 成本是在 k = 0 时。
这里有一个可爱的小技巧，我们可以使用它来使这个总和更容易处理。 log 函数增长得非常非常慢，非常慢，事实上，我们可以说 log n = o(nε) 对于任何 ε > 0。那么如果我们尝试通过将 lg (n / 2k) 替换为 (n / 2k)ε[= 来上限求和90=] 对于一些非常小但正的 ε？那么，我们会得到
T(n) = n sum from i = 0 to lg n (5/2)k lg(n/2k)
= O(n sum from i = 0 to lg n (5/2)k (n / 2k)ε)
= O(n sum from i = 0 to lg n (5/2)k nε (1 / 2ε)k)
= O(n1+ε sum from i = 0 to lg n (5 / 21+ε))
这可能看起来像是某种魔法，但这种技术——用非常小的多项式代替原木——是一个很好的方法，可以放在你的后兜里。它往往会出现在很多情况下！
我们这里的表达方式可能看起来比我们开始时的表达方式差很多，但它会变得更好。假设我们选择的 ε 足够小——比如，5 / 21+ε 大于 1。然后，内部求和再次是几何级数的总和，因此我们将其简化为
((5/21+ε)lg n + 1 - 1) / (5/21+ε - 1)
= O((5/21+ε)lg n)
= O(nlg (5/21+ε)) (using our trick from before)
= O(nlg 5 - 1 - ε)
这很好，因为那时我们的整体运行时间是
T(n) = O(n1+ε nlg 5 - 1 - ε)
= O(nlg 5),
你已经有了上限！
总结一下：
可以使用几何级数和的公式以及 alogb c = clogb a.
但是，这不会给你一个严格的上限，因为你的原始总和与你从递归方法得到的结果略有不同。
通过使用递归方法重复分析，您会得到更严格的总和，但更难求值。
我们可以通过使用 log n = o(nε) 对于任何 ε > 0 的事实来简化求和，并用它来重新调整求和以使其更易于操作。
有了这种简化，我们基本上使用与以前相同的技术重新进行分析 - 几何级数的总和，交换指数和对数中的项 - 以得出结果。
希望对您有所帮助！
所以这可能很愚蠢，但我坚持使用这种递归 T(n) = 5T(n/2) + O(nlogn)。我从 Master Theorem 知道它应该是
到目前为止我达到了
我只是想知道我的方向是否正确
您绝对是在正确的轨道上！让我们看看是否可以简化该求和。
首先，请注意您可以从求和中提取 log n 项，因为它独立于求和。这给了我们
(n log n) (sum from k = 0 to lg n (5/2)k)
那个和是一个几何级数的和，所以它解为
((5/2)log n + 1 - 1) / (5/2 - 1)
= O((5/2)lg n)
在这里，我们可以使用（可爱的）恒等式 alogb c = clogb a 重写
O((5/2)lg n) = O(nlg 5/2)
= O(nlg 5 - 1)
将其代入我们的原始公式可以得到
n log n · O(nlg 5 - 1) = O(nlg 5 log n).
嗯，这不太奏效。不过，我们真的非常接近在这里工作的东西！一个很好的问题是 为什么 这不起作用，为此，我们必须首先回到您如何获得原始求和的问题。
让我们尝试使用递归方法展开递归T(n) 的一些项。第一次扩展给我们
T(n) = 5T(n / 2) + n log n.
下一个是有趣的地方：
T(n) = 5T(n / 2) + n log n
= 5(5T(n / 4) + (n / 2) log (n / 2)) + n log n
= 25T(n / 4) + (5/2) log (n / 2) + n log n
然后我们得到
T(n) = 25T(n / 4) + (5/2) log (n/2) + n log n
= 25(5T(n / 8) + (n / 4) log (n / 4)) + (5/2) log (n/2) + n log n
= 125T(n / 8) + (25/4)n log (n / 4) + (5/2) log (n/2) + n log n
这里的一般模式似乎是以下总和：
T(n) = sum from i = 0 to lg n (5/2)kn lg(n/2k)
= n sum from i = 0 to lg n (5/2)k lg(n/2k)
请注意，这不是您的原始总和！特别要注意的是，对数项不是 log n，而是一个增长速度比它慢得多的函数。事实上，随着 k 变大，对数项变得非常非常小。事实上，如果您考虑一下，我们唯一一次真正支付全部 lg n 成本是在 k = 0 时。
这里有一个可爱的小技巧，我们可以使用它来使这个总和更容易处理。 log 函数增长得非常非常慢，非常慢，事实上，我们可以说 log n = o(nε) 对于任何 ε > 0。那么如果我们尝试通过将 lg (n / 2k) 替换为 (n / 2k)ε[= 来上限求和90=] 对于一些非常小但正的 ε？那么，我们会得到
T(n) = n sum from i = 0 to lg n (5/2)k lg(n/2k)
= O(n sum from i = 0 to lg n (5/2)k (n / 2k)ε)
= O(n sum from i = 0 to lg n (5/2)k nε (1 / 2ε)k)
= O(n1+ε sum from i = 0 to lg n (5 / 21+ε))
这可能看起来像是某种魔法，但这种技术——用非常小的多项式代替原木——是一个很好的方法，可以放在你的后兜里。它往往会出现在很多情况下！
我们这里的表达方式可能看起来比我们开始时的表达方式差很多，但它会变得更好。假设我们选择的 ε 足够小——比如，5 / 21+ε 大于 1。然后，内部求和再次是几何级数的总和，因此我们将其简化为
((5/21+ε)lg n + 1 - 1) / (5/21+ε - 1)
= O((5/21+ε)lg n)
= O(nlg (5/21+ε)) (using our trick from before)
= O(nlg 5 - 1 - ε)
这很好，因为那时我们的整体运行时间是
T(n) = O(n1+ε nlg 5 - 1 - ε)
= O(nlg 5),
你已经有了上限！
总结一下：
可以使用几何级数和的公式以及 alogb c = clogb a.
但是，这不会给你一个严格的上限，因为你的原始总和与你从递归方法得到的结果略有不同。
通过使用递归方法重复分析，您会得到更严格的总和，但更难求值。
我们可以通过使用 log n = o(nε) 对于任何 ε > 0 的事实来简化求和，并用它来重新调整求和以使其更易于操作。
有了这种简化，我们基本上使用与以前相同的技术重新进行分析 - 几何级数的总和，交换指数和对数中的项 - 以得出结果。
希望对您有所帮助！