是否可以解决递推关系
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 = 2lg n
那么在每次递归调用时,n 都会取其平方根。这相当于将上述指数减半,因此经过 k 次迭代后我们得到
n1/(2k) = 2lg n/(2k)
我们想在小于 2 时停止,给出
2lg n/(2k) = 2
lg n/(2k) = 1
lg n = 2k
lg lg n = k
因此,在 lg lg n 次平方根迭代之后,递归停止。并且,由于在每个级别递归的工作时间为 O(n),因此总运行时间为 O(n lg lg n)。
更一般地说,就像任何反复将其输入大小减半的算法都会让您想到“log n”一样,任何通过取平方根反复减少其输入大小的算法都会让您想到“log log n”。例如,van Emde Boas 树就使用这种递归。
有趣的是,这种递归用于获取著名算法的运行时间,该算法用于确定性地解决最近点对问题,假设计算机可以在恒定时间内取任意实数的下限。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)