algorithm - 如何使用递归求解 T(n) = 5T(n/2) + O(nlogn)

Question

所以这可能很愚蠢，但我坚持这个递归 T(n) = 5T(n/2) + O(nlogn)。我从 Master Theorem 知道它应该是 ，但我真的无法到达那里。

到目前为止，我达到了 的地步

我只是想知道我的方向是否正确

Answer 1

您绝对是在正确的轨道上!让我们看看是否可以简化该求和。

首先，请注意您可以从求和中提取 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})

在这里，我们可以使用(可爱的)恒等式 a^{log_b c} = c^{log_b a} 重写

O((5/2)^{lg n}) = O(n^{lg 5/2})

= O(n^{lg 5 - 1})

然后将其插入到我们的原始公式中可以得到

n log n · O(n^{lg 5 - 1}) = O(n^{lg 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/2^k)

= n sum from i = 0 to lg n (5/2)^k lg(n/2^k)

请注意，这不是您的原始金额!特别要注意的是，对数项不是 log n，而是一个增长速度比它慢得多的函数。事实上，随着 k 变大，对数项变得非常非常小。事实上，如果您考虑一下，我们唯一真正支付全部 lg n 成本的时间是 k = 0 时。

这里有一个可爱的小技巧，我们可以使用它来使这个总和更容易处理。 log 函数增长得非常非常慢，实际上，我们可以说 log n = o(n^ε) 对于任何 ε > 0。那么如果我们尝试 upper- 会发生什么？通过用 (n/2^k)^ε 替换 lg (n/2^k) 来限制这个总和，以获得一些非常小但正的 ε？好吧，那么我们会得到

T(n) = n sum from i = 0 to lg n (5/2)^k lg(n/2^k)

= O(n sum from i = 0 to lg n (5/2)^k (n / 2^k)^ε)

= O(n sum from i = 0 to lg n (5/2)^k n^ε (1 / 2^ε)^k)

= O(n^1+ε sum from i = 0 to lg n (5 / 2^1+ε))

这可能看起来像是某种巫术，但这种技术——用非常小的多项式代替原木——是一个很好的方法，可以放在你的后兜里。它往往会出现在很多情况下!

我们这里的表达方式可能看起来比我们开始时的要糟糕得多，但它会变得更好。假设我们选择的 ε 足够小 - 比如，5/2^1+ε 大于 1。然后，内部求和再次是几何级数的总和，因此我们将其简化为

((5/2^1+ε)^{lg n + 1} - 1) / (5/2^1+ε - 1)

= O((5/2^1+ε)^{lg n})

= O(n^{lg (5/21+ε)}) (using our trick from before)

= O(n^{lg 5 - 1 - ε})

那太好了，因为那时我们的整体运行时间是

T(n) = O(n^1+ε n^{lg 5 - 1 - ε})

= O(n^{lg 5}),

你已经有了上限!

总结:

• 可以使用几何级数和的公式以及 a^{log_b c} = c< sup>log_b a.

• 但是，这不会给您一个严格的上限，因为您的原始总和与您从递归方法得到的总和略有不同。

• 通过使用递归方法重复分析，您会得到更严格的总和，但也更难评估。

• 我们可以通过对任何 ε > 0 使用 log n = o(n^ε) 这一事实来简化求和，并使用它来重新调整求和以使其更易于操作.

• 有了这种简化，我们基本上使用与以前相同的技术重新进行分析 - 几何级数的总和，交换指数和对数中的项 - 以得出结果。

希望这对您有所帮助!