algorithm - この再帰関係の解き方: T(n) = 4*T(sqrt(n)) + n

Question

マスターメソッドを使用して再帰関係を解決する方法を知っています。また、以下の再発を解決する方法も知っています。

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

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

上記の 2 つの繰り返しでは、再帰ツリーの各レベルで同じ量の作業が行われます。また、再帰ツリーには合計 n レベルのログ ログがあります。

これを解決するのに問題があります: T(n) = 4*T(sqrt(n)) + n

編集: ここで n は 2 の累乗です

Answer 1

n = 2^k とします。T(2^k) = 4*T(2^(k/2)) + 2^k です。S(k) = T(2^k) とします。S(k) = 4S(k/2) + 2^k です。Mater Theorem を使用すると、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) を意味します。

Answer 2

これを解決するのに問題があります：T（n）= 4 * T（sqrt（n））+ n

編集：ここでnは2の累乗です

この編集は重要です。したがって、再発が2で停止するとします。

したがって、問題は、再帰ツリーの深さです。これは、nが十分に小さくなる（たとえば2未満になる）前にnの平方根を取ることができる回数です。私たちが書くなら

n = 2 ^{lg n}

次に、再帰呼び出しごとに、nの平方根が取得されます。これは、上記の指数を半分にすることと同じです。したがって、k回の反復の後、次のようになります。

n ^{1 /（2 k）} = 2 ^{lg n /（2 k）}

これが2未満になったときに停止したいので、

2 ^{lg n /（2 k）} = 2

lg n /（2 ^k）= 1

lg n = 2 ^k

lg lg n = k

したがって、lg lg n回の平方ルート化の後、再帰は停止します。（ソース）

再帰ごとに4つの新しいブランチがあり、ブランチの合計は4 ^（ツリーの深さ）です4^(lg lg n)。

編集：

ソース

Answer 3

   T(n) = 4 T(sqrt(n)) + n
   4 [ 4 T(sqrt(sqrt(n) + n ] + n
   4^k * T(n^(1/2^k)) +kn because n is power of 2.
   4^k * T(2^(L/2^k)) +kn   [  Let n = 2^L , L= logn]
   4^k * T(2) +kn   [  Let L = 2^k,  k = logL = log log n]
   2^2k * c +kn
   L^2 * c + nloglogn 
   logn^2 * c + nloglogn
   = O(nloglogn)