InverseDa's Blog

预备知识：

①积分近似：

$$\sum_{i=0}^nf(i)\sim\int_{i=0}^{i=n}f(i) di$$

​ 一般地：

$$\sum_{i=0}^nf(i)\le\int_{i=0}^{i=n}f(i) di$$

②分治递归式通解：（主定理的原式）

$$T(n)=aT(n/b)+f(n)$$

​ 通解为：

$$T(n)=\Theta(n^{\log_ba})+ \sum_{i=0}^{\lceil\log_bn\rceil}a^if(n/b^i)$$

​ 其中$\lceil\log_bn\rceil=[\log_bn]-1$，求和部分直接用积分近似计算即可