以下与平方根的递归关系的解是什么:T(n)= T([√n])+ logn？

Question

我知道有一个类似的问题但是+1.我想知道如果我们在那里有对数函数我们将如何进行？

我觉得你会尝试进入基本情况T(n ^ 1/2 ^ k)+ log(n ^((2 ^ k - 1)/(2 ^ k-2 ^ k-1)).

但是你在这之后做了什么？

Answer 1

尝试扩大重复次数:

T(n) = T(n^0.5) + log(n) =
     = T(n^0.25) + log(n^0.5) + log(n) =
     = T(n^0.25) + 0.5 log(n) + log(n) =
     = ...

因此,写这种重复的另一种形式是

(1 + 0.5 + 0.25 + ...) * log(n) = 2 log(n)