T(n) = cT(n^(0.5)) + n其中c是常数c>0。
我什么都试过了，但找不到解决办法。
欢迎任何帮助，谢谢。
最佳答案
它是线性的。
假设存在一些K这样所有T(n) <= Kn的n < M
然后T(M) <= cKsqrt(M) + M <= KM
对于足够大的K (and M)，这是正确的。So T(n) = O(n)。
显然T(n) = Omega(n)。
所以T(n) = Theta(n)。
关于algorithm - 如何计算以下递归关系，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22458815/