迭代法
每一次对过程的重复称为一次迭代，而每一次迭代得到的结果会作为下一次迭代的初始值。重复执行一系列运算步骤，从前面的量依次求出后面的量的过程。
例1
problem:
\(T(n)=2 \times T(\frac{n}{4})+ \sqrt n,T(1)=1\)
solution:
\[T(n)=2 \times T(\frac{n}{4})+ \sqrt n \]\[T(n)=2 \times (2 \times T(\frac{n}{16})+\sqrt \frac{n}{4})+ \sqrt n \]\[T(n)=4 \times T(\frac{n}{16})+2 \times \frac{\sqrt n}{2}+ \sqrt n \]\[T(n)=4 \times T(\frac{n}{16})+2 \sqrt n \]\[\ldots \]\[T(n)=2^k \times T(\frac{n}{2^{2k}})+k \sqrt n \]令 \(2^{2k}=n\)，即 \(2^k=\sqrt n\)，\(k=\log_2^{\sqrt n}=\log_2^{n^{\frac{1}{2}}}=\frac{1}{2} \log_2^n\)
\[T(n)=\sqrt n \times T(1)+\frac{1}{2} \log_2^{n} \sqrt n \]\[T(n)=\sqrt n +\frac{1}{2} \sqrt n \log_2^n \]所以时间复杂度为 \(O(\sqrt n \log n)\)
标签：frac,log,递归,求解,复杂度,16,sqrt,times From： https://www.cnblogs.com/reclusive2007/p/17701395.html