与函数增长速度相关的记号

总结：上述的五个记号作用于某个函数g时，便会产生相应的函数集合，它们之中的$\Theta、O、 \Omega$都只给出一个上界或下界的存在性（上界或下界用来估算最糟糕或最好的情况时算法的性能），而$o、\omega$则给出了更严格的限制，即集合中的函数满足相应的极限条件，表示在问题规模（用n来衡量）很大时算法的性能表现。

主定理

分而治之的核心思想是寄希望于所求解问题可以在付出一定代价后被拆分为规模更小的子问题，其中的子问题与原问题应该是同质的，也就是说除了规模大小和具体的输入不同外，问题的其他方面并无变化，这保证了可以用相同的方法求解拆分后的子问题。分而治之思想的一个经典例子是归并排序（它由冯诺依曼提出），该算法将一个数组的排序问题递归地拆分为两个子问题，即左边的半个数组的排序问题和右边的半个数组的排序问题，拆分的代价指将原问题拆分为子问题的代价加上通过子问题的解来得到原问题的解的代价。在这个问题中，算法的时间复杂度（指算法在最坏的情况下的运行时间）满足递归表达式：

$$ T(n)=\left\{\begin{aligned}&2T(n/2)+\Theta(n),n > 1\\&\Theta(1), n = 1\end{aligned}\right. $$

通过展开递归表达式我们可以T(n)最终的表达式$T(n)=\Theta(n\lg{n})$。在许多问题中，尽管通过分而治之的思想得到递归表达式各种各样，但其中很多都满足$T(n)=aT(n/b)+f(n)$的形式，即该算法将原问题分解为a个子问题，每个子问题的问题规模为$n/b$，拆分的代价为$f(n)$。

于是，如何求解具有该形式的递归表达式便成为了一个人们很关心的问题，这个问题的解决方式有以下几种：

其中代入法是通过猜测并验证解来求解，画出递归树是将递归过程展开为一颗递归树，并对各个节点的代价求和，而主定理法则是通过数学证明来得到递归表达式的解。这里给出主定理：

令$a\ge1$和$b>1$是常数，$f(n)$是一个函数，$T(n)$是定义在非负整数上的递归式，它们满足如下关系：

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

其中我们将$n/b$解释为$\lfloor n/b \rfloor$ 或$\lceil n/b \rceil$。那么$T(n)$有如下渐进界：

  1. 若对某个常数$\epsilon>0$有$f(n)=O(n^{\log_{b}{a}-\epsilon})$，则$T(n)=\Theta(n^{\log_{b}{a}})$；
  2. 若$f(n)=\Theta(n^{\log_{b}{a}})$，则$T(n)=\Theta(n^{\log_{b}{a}}\lg{n})$;
  3. 若对某个常数$\epsilon>0$有$f(n)=O(n^{\log_{b}{a}+\epsilon})$，且对某个常数$c<1$和所有足够大的$n$有$af(n/b)\le cf(n)$，则$T(n)=\Theta(f(n))$。

分而治之的例子