初赛题目（个人笔记12）

#### 初赛 / 复杂度类题 / 主定理 / 数列 例题：$$ T(n)=T(n/2)+nlogn $$ 如果在一个复杂度 $ T(n)=aT(n/b)+f(n) $ 中 $ f(n) $ 内有log级别的，是不能直接用主定理的，因为logn没办法表示成$ c(n^d) $ 的形式，所以这怎么办？ #### 解题步骤: $1.$用另一个数代替$logn$,例如用$m$代替$logn$,这样就可以得到一个新的递推式 $2.$而我们发现$T(n)$的部分会变成$T(2^m)$,那么就用另一个函数代替 例如$S(m)=T(2^m)$ $3.$然后就可以得到一个没有$log$存在的复杂度递推式,求解 $4.$最后一步步推回到$T(2^m)$,$T(n)$,得出最后答案 ------------ ##### _第一步骤:_ 我们可以转换一下，设 $ m=logn $，则有： $$ T(2^m)=T(2^{m-1})+m×2^m $$ ##### _第二步骤:_ $$ S(m)=T(2^m) $$ ##### _第三步骤_ $$ S(m)=S(m-1)+m×2^m $$ 可以发现，$S(m)$绝对是$S(m-1)$的$2$倍以上 设$f(m)=m×2^m$ 所以可以看成:$S(m)=f(m)+f(m)/2+f(m)/4+f(m)/8+......$ --------- *插入:* $$ 1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+...+\frac{1}{2^n}≈2$$ *可以看成二进制数: $1.111111 ....$* -------- $$ 所以S(m)的复杂度就是2f(m),即m×2^m(忽略常数...) $$ ##### _第四步骤:_ $$ T(2^m)=S(m)=m×2^m $$ $$ T(n)=T(2^m)=(logn)×(n) $$ 即 $ T(n)=nlogn $ END