应用f（n）= 2 ^ n的大师定理 [英] Applying Master's Theorem with f(n) = 2^n

问题描述

我正在尝试将Master定理应用于此类重复发生：

I am trying to apply the Master's Theorem to a recurrence of this type:

T（n）= T（n / 2 ）+ 2 ^ n

T(n) = T(n/2) + 2^n

但是，f（n）= 2 ^ n似乎不适合上述三种情况在大师定理中，它们似乎都以n为底，而不是以2为底。如何解决这种类型的重复出现，有人可以帮忙吗？谢谢。

However, f(n) = 2^n doesn't seem to fit any of the three cases described in the master's theorem, which all seem to have base n instead of base 2. How can I solve a recurrence of this type, could anyone please help ? Thanks.

推荐答案

如果该定理的所有情况都不适用，则该定理将无法解决您的重现问题。

If none of the cases of the theorem applies, then the theorem won't solve your recurrence. It can't solve every single recurrence out there.

要解决您的问题：反复替换递归可以得到什么的情况是T（n）= 2 ^ n + 2 ^（n / 2）+ 2 ^（n / 4）+ ... + 2，并且由于有n个要累加的项，您最终会得到一些结果低于2 ^（n + 1），因此您的总收入为Θ（2 ^ n）。

To address your issue: what you get by repeatedly substituting the recursive case is T(n) = 2^n + 2^(n/2) + 2^(n/4) + ... + 2, and since there are log n many terms to add up, you end up with something below 2^(n+1), so in total you're in Θ(2^n).

这篇关于应用f（n）= 2 ^ n的大师定理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！