math - 再帰関係を解く T(n) = √n T(√n) + n

Question

再帰関係を解くことはできますか？

T(n) = √n T(√n) + n

マスター定理を使用していますか? 形ではありません

T(n) = a ⋅ T(n / b) + f(n)

しかし、この問題は CLRS 第 4 章の演習で与えられます。

Answer 1

これはマスター定理では解決できません。ただし、再帰ツリー法を使用して O(n log log n) に解決できます。

この背後にある直感は、ツリーの各レベルで n 個の作業を行っていることに気付くことです。トップレベルは明示的に機能しません。√n 部分問題のそれぞれは、正味合計 n の作業に対して √n の作業を行います。これは、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 回繰り返した後、再帰は停止します。そして、各レベルで再帰は O(n) の作業を行うため、総実行時間は O(n lg lg n) です。

より一般的には、入力サイズを半分に繰り返し削減するアルゴリズムが「log n. たとえば、van Emde Boas ツリーはこの再帰を使用します。

興味深いことに、この再帰は、コンピューターが一定時間内に任意の実数の下限を取ることができると仮定して、最も近い点のペアの問題を決定論的に解くための有名なアルゴリズムの実行時間を取得するために使用されます。