是否可以解决递归关系
T(n) = √n T(√n) + n
使用主定理?它不是形式
T(n) = a ⋅ T(n / b) + f(n)
但是这个问题是在 CLRS 第 4 章的练习中给出的。
是否可以解决递归关系
T(n) = √n T(√n) + n
使用主定理?它不是形式
T(n) = a ⋅ T(n / b) + f(n)
但是这个问题是在 CLRS 第 4 章的练习中给出的。
这是主定理无法解决的。但是,它可以使用递归树方法解决,以解决 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”一样,任何通过取平方根反复减少其输入大小的算法都应该让您想到“log log n”。例如,van Emde Boas 树使用这种递归。
有趣的是,这种递归用于获得著名算法的运行时间,该算法用于确定性地解决最接近的点对问题,假设计算机可以在恒定时间内占用任意实数的地板。