柒葉灬 的博客

柒葉灬 的博客

初赛题目(个人笔记12)

posted on 2018-10-11 21:06:29 | under 初赛/计算复杂度/数列 |

初赛 / 复杂度类题 / 主定理 / 数列

例题: $$ 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