如何解决这个递推关系：T（N）= 4 * T（开方（N））+ N [英] How to solve this recurrence relation: T(n) = 4*T(sqrt(n)) + n

问题描述

我知道如何解决使用主法的递推关系。 此外，我所知道的如何解决下面的复发：

I know how to solve the recurrence relations using Master Method. Also I'm aware of how to solve the recurrences below:

T（N）=开方（N）* T（开方（N））+ N

T(n) = sqrt(n)*T(sqrt(n)) + n

T（N）= 2 * T（开方（N））+ LG（N）

T(n) = 2*T(sqrt(n)) + lg(n)

在上面的两个复发有工作在递归树的每个级别相同。还有一个总的日志日志N级的递归树的。

In the above two recurrences there is same amount of work at each level of the recursion tree. And there are a total of log log n levels in the recursion tree.

我在解决这个麻烦： T（N）= 4 * T（开方（N））+ N

I'm having trouble in solving this one: T(n) = 4*T(sqrt(n)) + n

编辑： 这里，n是2的幂

推荐答案

假设N = 2 ^ķ。我们有T（2 ^ K）= 4 * T（2 ^（K / 2））+ 2 ^ķ。令S（k）的= T（2 ^ k）的。我们将S（k）= 4S（K / 2）+ 2 ^ķ。通过使用母校定理，我们得到S（K）= O（2 ^ K）。由于S（K）= O（2 ^ k）和S（K）= T（2 ^ K），T（2 ^ K）= O（2 ^ K），这意味着T（N）=为O（n）。

Suppose that n = 2^k. We have T(2^k) = 4*T(2^(k/2)) + 2^k. Let S(k) = T(2^k). We have S(k) = 4S(k/2) + 2^k. By using Mater Theorem, we get S(k) = O(2^k). Since S(k) = O(2^k) and S(k) = T(2^k), T(2^k) = O(2^k) which implies T(n) = O(n).

这篇关于如何解决这个递推关系：T（N）= 4 * T（开方（N））+ N的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！