Which one of the following is the lowest upper bound of
T(n).
T
(
n
)
for the following recursion
T
(
n
)
=
2
T
(
√
n
)
+
lo
g
n
?
(4分)
设 m = logn, 则2^m = n.
T(2^m) = 2T(2^(m/2))) + m
设 G(m) = T(2^m)，则原式转化为G(m) = 2G(m/2) + m
根据主定理，a = 2, b = 2, k = 1, p = 0. a = b^k，满足条件2，所以算法复杂度为O（mlogm）
又因为 m = logn,所以算法复杂度为O（logn loglogn )
附：主定理
