math - 无法理解对数转换

Question

我正在浏览一个算法类的幻灯片，并遇到了以下问题。

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

重命名：m = lg n => n = 2^m T (2^m) = 2T(2^(m/2)) + m

重命名：S(m) = T(2^m) S(m) = 2S(m/2) + m

谁能解释一下最后一个等式是怎么来的？我无法理解 S(m/2) 是怎么来的。谢谢你。

Answer 1

这只是一个参数替换。

你有S(m) = T(f(m)), where f(m) = 2^m. 用 m/2 代替 m，你会得到

S(m/2) = T(f(m/2)), f(m/2) = 2^(m/2)

现在你可以重写左边的部分T(f(m/2)) = T(2^(m/2)) = S(m/2)