如何解决递归T(n)= 2T(n ^(1/2))+ log n？

Question

我试图找到重现的时间复杂性:

T(n)= 2T(n ^1/2)+ log n

我非常接近解决方案,但是,我遇到了障碍.我需要解决:

n ^{(1/2 ^k)} = 1

为了简化我的替换模式.我不是在寻找复发的答案,只是一个解决方案k.

Answer 1

当您开始展开递归时，您将获得：

这是同一件事，但有几个附加步骤：

现在使用边界条件进行递归（将数字2选为0和1没有意义），您将获得：

代k入方程式，您将得到：

这是使用相同想法的几个递归。