杜教筛时间复杂度证明

假设我们要求$S(n)$且有$S(n)=sum_{i=2}^nS(⌊frac ni⌋)$
于是我们要求在整除分块优化下的时间复杂度,只需要求出$sqrt n个S(⌊frac ni⌋)$的值就行了

假设计算出$S(n)$的复杂度为$T(n)$,则有
$T(n)=Theta (sqrt n) + sum_{i=2}^n(T(i)+T(frac ni))$其中$Theta (⌊sqrt n⌋)$是累加也就是合并的时间

这里其实只用展开一层就行了,因为在往下就是高阶小量,所以有
$T(n)=Theta(sqrt n) + sum_{i=2}^n(Theta (sqrt i)+Theta(sqrt{⌊frac ni⌋}))=Theta(n^{frac 34})$$ecause Theta (sqrt i)+Theta(sqrt{⌊frac ni⌋})>=2sqrt{sqrt n}=2n^{frac 14}$
$herefore sqrt n(Theta (sqrt i)+Theta(sqrt{⌊frac ni⌋}))>=2n^{frac34}$

又由于可以用筛法处理一部分,假设处理了前$k$个前缀和,且$k>=sqrt n$,则$T(n)=sum_{i=2}^{frac nk}Theta(sqrt{⌊frac ni⌋})=Theta(frac n{sqrt k})$当$k$取到$Theta(n^{frac 23})$时能取到较优秀的时间复杂度$Theta(n^{frac 23})$