基础内容： $$ 假设 f(n)为求解问题的规模的总步数，g(n)表示每一步中额外的步骤。\ 假设递推关系中，每次都将问题拆分为d个更小的问题，那么\ f(n)=f(\frac{n}{d})+g(n) $$ 例如归并排序
其总数就可以表示为f(n)=2f(n/2)+n
在上面的基础之上：
“ $$ 设f是满足递推关系：\ f(n)=af(\frac{n}{b})+c \ 的增函数，即g(n)为固定长度，其中 a,c \in R， b \in N，那么 \ f(n) 是 \begin{cases} O({n}^{\log_{b} a}) & a>1 \ O(\log_b n) & a=1 \end{cases} \ 如果 n=b^k,a \neq 1,f(n)=C_1 {n}^{\log_b a}+C_2\ C_1=f(1)+\frac{c}{a-1}，C_2=\frac{-c}{a-1} $$ ”
先来证明大O表示法所对应的值来源： $$ f(n)=af(\frac{n}{b})+g(n)\ =a(af(\frac{n}{b^2})+g(\frac{n}{b}))+g(n)\ =a^3 f(\frac{n}{b^3})+a^2 g(\frac{n}{b^2})+ag(\frac{n}{b})+g(n)\ \vdots \ =a^k f(\frac{n}{b^k})+\sum^{k-1}{j=0}a^j g(\frac{n}{b^j})\ 因为 \frac{n}{b^k}=1，所以 \ f(n)=a^k f(1)+\sum^{k-1}{j=0}a^j g(\frac{n}{b^j}) $$ 在上面的基础之上，再进行接下来的内容： $$ 令 n=b^k，同时假设 g(n)=c。\ 于是上面的式子就可以替换成：\ f(n)=a^k f(1)+c\sum_{j=0}^{k-1} a^j\ 当 a=1时，f(n)=f(1)+ck=f(1)+c \log_b n，所以 O(\log_b n)\ 当 a>1时，f(n)=a^k f(1)+c \cdot \frac{a^k-a}{a-1}\ =a^k f(1)+ c \frac{a^k}{a-1}-c\frac{a}{a-1} \ =a^k (f(1)+c \frac{1}{a-1})-c\frac{a}{a-1} \ 令 C_1=f(1)+c \frac{1}{a-1}，且 C_1 肯定是实数\ 同理令 C_2=c\frac{a}{a-1}，且 C_2 \in R，所以 \ f(n)=a^k \cdot C_1-C_2，所以 O({n}^{\log_{b} a}) $$ 几何序列求和的公式见这里
这里再说明一下上面的a>1时，大O值的由来：
$$
a^k={a}^{\log_b n}={n}^{\log_b a}，这里采用的是对数函数的互换性质。
$$
附录：对数函数互换性质证明
$$
先证明一个性质：k \cdot \log_b M=\log_b M^k。\
证明：令 a=\log_b M^k，所以 b^a={M}^{k}，即 b={M}^{\frac{k}{a}}，\
所以 \log_{b} M=\frac{k}{a}，即 a \log_{b} M=k
$$
在上面那条性质的基础之上，再来证明下面这个：
$$
{M}^{\log_{a} N}={N}^{\log_{a} M}，称为互换的形式。\
证明：\ 令 a^k=N，所以 {N}^{\log_{a} M}={a}^{k \log_{a} M}= M^k={M}^{\log_a N}
$$
在上面我们假定了g(n)的长度为固定值，下面开始讨论如果g(n)的长度与n有关。
“ $$ 设f是满足递推关系：\ f(n)=a f(\frac{n}{b})+c n^d\ 其中 a,b,c,d \in R\ f(n)是 \begin{cases} O(n^d) & a<b^d\ O(n^d \log_b n) & a=b^d\ O({n}^{\log_b a}) & a>b^d \end{cases} $$ ”
这个的证明我能力不足，解不开。