封面来源

Pixiv 暮れる空-94961680

[toc]

前置芝士

高中数学，可能会需要一点高等数学的知识

内容

假设有递推关系式$T(n)=aT(\frac n b)+f(n)$，其中$n$为数据规模，$a$为递推的子问题数量，$\frac n b$为每一个子问题的规模（假设子问题规模基本一样），$f(n)$为递推以外的计算工作。

$a \geq 1,b>1$为常数，$T(n)$为非负整数，则有以下结论

1.若$f(n)=O(n^{\log_b{a-\epsilon}}),\epsilon>0$，则$T(n)=\Theta(n \log_b a)$

2.若$f(n)=\Theta(n^{\log_b a})$，则$T(n)=\Theta(n^{\log_b a}\log n)$

3.若$f(n)=\Omega(n^{log_b a+\epsilon})\epsilon>0$，且对于某个常数$c<1$和所有充分大的$n$有$af(\frac n b)\leq c f(n)$，则$T(n)=\Theta(f(n))$。

看上去很复杂？

其实主定理就是用一个近似函数来描述一个复杂的递推函数的表达式。