即高中经常用的换元法。
直接看两个例子吧！
考虑递推式
$$f(n) = \begin{cases}
1 & n=2 \\
1 & n = 4 \\
f(n/2)+f(n/4) & n>4
\end{cases}$$
解：
这里假设 $n$ 是2的幂，令 $t = log \ n, \ g(k) = f(2^k)$
那么
$$g(k) = \begin{cases}
1 & n=2 \\
1 & n = 4 \\
g(k-1)+g(k-2) & n>4
\end{cases}$$
根据Fibonacci的递推式，$g(k) = \phi ^k,\ \phi = \frac{1+\sqrt5}{2}$
所以 $f(n) = g(log \ n) = \phi^{log\ n} = n^{log \ \phi } = \Theta(n^{0.69})$.
考虑递推式
$$f(n) = \begin{cases}
d & n=2 \\
2f(\sqrt n) + b log \ n& n>2
\end{cases}$$
解：
设 $n = 2^{2^k}$，则 $k = loglogn, g(k) = f(2^{2^k})$.
$f(n)$ 可重写成
$$g(k))\begin{cases}
d & k=0 \\
2g(k-1)+b2^k & k>0
\end{cases}$$
易求 $g(k) = d2^k + bk2^k$
因此 $f(n) = g(loglogk) = d*\ logn + b*\ logn* \ loglogn$.
原文：https://www.cnblogs.com/lfri/p/11632420.html