如何解决以下递归关系？
How to solve the below Recurrence relation?
考虑 link 中提供的递归方程。这不符合主定理所要求的形式。我不想使用替换方法，因为它很耗时。我也厌倦了改变变量 (k=2^m)，但失败了。
如何通过递归树或迭代方法解决这个问题？
T(n) =n^0.5 T(n^0.5) + n
p.s :
预期的解决方案是：O(nlglgn)
令 U(n) = T(n)/n。
那么U(n) = n1/2T(n1/2)/n + 1,等等
U(n) = T(n1/2)/n1/2 + 1
U(n) = U(n1/2) + 1
通过迭代法很容易找到U(n) <= log log n + U(2)，因为这就是在得到2之前你可以对n求平方根的次数（使用日志基地 2)。然后，如果需要，您可以对所有 n > 2 进行归纳证明。
因此你有 T(n) = U(n)*n <= n (log log n + T(2)/2)，这是 O(n log log n)
考虑 link 中提供的递归方程。这不符合主定理所要求的形式。我不想使用替换方法，因为它很耗时。我也厌倦了改变变量 (k=2^m)，但失败了。
如何通过递归树或迭代方法解决这个问题？
T(n) =n^0.5 T(n^0.5) + n
p.s : 预期的解决方案是：O(nlglgn)
令 U(n) = T(n)/n。
那么U(n) = n1/2T(n1/2)/n + 1,等等
U(n) = T(n1/2)/n1/2 + 1
U(n) = U(n1/2) + 1
通过迭代法很容易找到U(n) <= log log n + U(2)，因为这就是在得到2之前你可以对n求平方根的次数（使用日志基地 2)。然后，如果需要，您可以对所有 n > 2 进行归纳证明。
因此你有 T(n) = U(n)*n <= n (log log n + T(2)/2)，这是 O(n log log n)