复杂度计算
①.主定理 （$T(n) = a T(\frac{n}{b}) + f(n) $ 型）
②. 分层 (\(T(n)=k\sqrt{n}T(\sqrt{n})+n\) 型)
相当于将 \(n\) 分成若干层,层数 \(c\)。
最底层的大小大约为2（因为大小为1时不好计算，且2很接近1了）
\[\Large (n^{\frac{1}{2}})^c=n^{\frac{1}{2^c}}=2
\]
\[\Large log_2 \ n^{\frac{1}{2^c}}=log_2 \ 2=1
\]
\[\Large \frac{1}{2^c}log_2 \ n=1
\]
\[\Large log_2 \ n=2^c
\]
\[\Large c=log_2\ log_2 \ n
\]
当 \(k=1\) 时：
\(\Large T(n)=c \times n=n\ log_2\ log_2\ n\)
当 \(k=4\) 时：
\(\Large T(n)=(1+4+4^2+4^3+4^4+\dots+4^{c-1})n\)
根据等比数列求和公式得
\(\Large T(n)=(4^c-1)n/3\)
去掉常数得
\(\Large T(n)=4^c\ n\)
\[\Large 4^c=4^{log_2\ log_2\ n}=(2^{log_2\ (log_2\ n)})^2=log^2_2\ n
\]
\(\Large T(n)=n\ log^2_2\ n\)