求解递归关系T(n)=√nT(√n)+ n

Question

是否有可能解决递归关系

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

使用主定理？它不是形式

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

但这个问题是在CLRS第4章的练习中给出的.

Answer 1

主定理无法解决这个问题.但是,可以使用递归树方法解析为O(n log log 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",任何通过取平方根反复削减其输入大小的算法都会让你想到"log log n.".例如,van Emde Boas树使用这种复发.

有趣的是,这种重复用于获得着名算法的运行时间,用于确定性地解决最接近的点对问题,假设计算机可以在恒定时间内取代任意实数的最低点.