给定递归关系的时间复杂度T（n）= T（√n）+ n

Question

有人可以帮我吗？>

给定的递归关系T(n)=T(√n)+n

我需要评估其时间复杂度。我做了以下事情：

given T(n)=T(√n)+n
        =>T(n-1)=T(√(n-1))+(n-1)  
        T(n)=T(sqrt(n-1))+(n-1)+n; 
        similarily evaluated T(n-2),
        T(n-3),.......

        => T(n)=T(√(n-k))+(n-k)+(n-(k-1))+.......+(n-1)+n
         assumed n-k=0
        =>n=k;
        =>T(n)=T(√(k-k))+(n-(n-1))+(n-(n-2))+......+(n-1)+n
        =>T(n)=T(0)+1+2+3+......+n
        =>T(n)=base case + Σn
        =>T(n)=constant + n(n+1)/2
        =>T(n)=O(n^2)
这是正确的吗？

有人可以通过给定的递归关系T（n）= T（√n）+ n来帮助我，我需要评估其时间复杂度。我做了以下工作：给定T（n）= T（√n）+ n => T（n-1）= T（√（n-1））+（n-1）T（...

Answer 1

根据答案here，您可以替代：

alt =“ d

所以我们有：然后重复将是：

然后我们可以更改表示形式：

并且根据Master's Theorem的第三种情况，时间复杂度将为：