前言

符号说明
下述例子， $T (n)$ 表示数据规模为 $n$ 的时间复杂度
$O (n)$ 表示大 $O$ 计数法，即最坏复杂度
下述例子默认边界条件 $T (1) = O (1)$
题目都为求解 $T (n)$ 的非递推公式。

题目

计算
$T(n)=F(n)+aT(\frac{n}{b})$
其中 $F (n)$ 为一个关于 $n$ 的简单函数。
这里简单函数：指幂函数、常函数，或上述函数的简单加减（多项式函数）。
我们通常使用 $P (x)$ 表示（虽然下文中都使用了 $F (x)$ ）
（更新）注：
指数函数和对数函数在这里不能使用本文提到的做法来做，原因在思考二中。

求
$T (n) = 2 T (n / 2)$
容易得到，是一个等比数列，首项为1，公比为2，递归层数为 $\lfloor \log_2n \rfloor +1$ 至 $T (0)$
即递归次数 $\lfloor \log_2n \rfloor$ 至 $T (1)$
$T(n)= O(2^{\log_2 n})=O(n)$
注：由于大 $O$ 计数法，忽略常数，若数不为2的幂次，应该计算得到为 $n\sim 2n$ 的一个数。
手模拟也可以得到， $T (1) = 1, T (2) = 2, T (4) = 4, e t c .$

求
$T (n) = F (n) + 2 T (n / 2)$
首先容易得到， $T (n)$ 是不低于 $O (n)$ 的，因为 $F (n) 至少 O (1)$
我们若只考虑 $2$ 的幂次
然后，由于每一次 $n\rightarrow n/2$ ，我们可以想到，迭代次数为 $\lfloor \log_2n \rfloor$ ，即上述等价于
$T_2(x)=F(2^x)+2T_2(x-1)$
其中 $T(n)=T_2(\lfloor \log_2n \rfloor)=T_2(log_2n)$ 因为我们只考虑 $2$ 的幂次。
由于数据规模越大， $F(2^x)$ 是应当越来越大的。
容易看出来，这是一个等比数列变种。我们设：
$T_2(x)+\frac{F(2^x)}{c} =2(T_2(x-1)+\frac{F(2^{x-1})}{c})\qquad 其中c 是常数\tag{1}$
通过移项，我们可以得到：
$\frac{2F(2^{x-1})-F(2^x)}{c}=F(2^x)$
即
$c=\frac{2F(2^{x-1})-F(2^x)}{F(2^x)}$
我们目前可以做的内容，就是 $F(n/2)F(2n)=(F(n))^2$ 情况下的分析。
这样的话， $c$ 就是一个常数。
对于幂函数，注意到，如果 $F(n)=an^b$ 的话是成立的。
由于我们是大 $O$ 计数，故只记录 $F (n)$ 的最高次项即可，忽略低次项。
可以看出来，分母大于 $1$ ，分母 $2F(2^{x-1})-F(2^x)$ 决定了 $c$ 的符号，或者 $c = 0$ 。

于是，我们由 $(1)$ 可以得到：
$\frac{T_2(x)+F(2^x)/c}{T_2(x-1)+F(2^{x-1})/c}=2$
设 $S(x)=T_2(x)+F(2^x)/c$ ，边界条件 $S(1)=T_2(1)+F(2)/c=O(1)+F(2)/c=o(1)$
得到： $S(x)=S(1)\times 2^{x-1}$
即我们得到了：
$S(x)=T_2(x)+F(2^x)/c=2^{x-1}\times o(1)\\ T_2(x)=2^{x-1}\times o(1)-F(2^x)/c$
我们转换为 $T (n)$ ，便得到了：
$\tag{2}$
我们得到了结论：
若 $c > 0$ ，那么 $T (n) = O (n)$
若 $c < 0$ ，那么 $T(n)=O(n-F(n)/c)=O(n+\cfrac{(F(n))^2}{F(n)-2F(n/2)})$

由于 $c = 0$ ，那么一定有 $F(2^x)=2F(2^{x-1})=2^{x-1}F(1)$
那么式子表示成：
$T_2(x)=2^{x-1}F(2^1)+2T_2(x-1)=2^x+2T_2(x-1)$
由于我们小学二年级就在《算法导论》¹学过这种式子怎么搞，很明显，我们可以看做一个塔，然后瞎搞去算。
但是我们之前学过优雅的 特征方程求解非齐次递推线性方程
特征方程为 $\lambda^2-2\lambda =0$ 得到 $\lambda_1=0,\lambda=2$
设递推方程通解为 $T_2(x)=c2^x$
由于非齐次项为 $2^x$ ，为一重根。
设递推方程通解为 $T_2(x)=c_12^x+c_2x2^x$
初始项为 $T_2(0)=0,T_2(1)=2$ ，得到 $T_2(x)=x2^x$
即 $T(n)=T_2(\log_2n)=O(\log_2n\times n)=O(n\log_2n)$

$c=\frac{2F(n/2)-F(n)}{F(n)}$
若 $c > 0$ ，那么 $T (n) = O (n)$
若 $c < 0$ ，那么 $T(n)=O(n-F(n)/c)=O(n+\cfrac{(F(n))^2}{F(n)-2F(n/2)})$
若 $c = 0$ ，那么 $T(n)=O(n\log_2n)$

求
$T (n) = a T (n / b)$
思路很简单，就是思考一的延伸。
递归层数为 $log_b n$ ，每次乘以 $a$ ，即：
$T(n)=O(a^{\log_bn})=O(a^{\cfrac{\log_an}{\log_ab}})=O(n^{\cfrac{1}{\log_ab}})$

即 $aF(b^{x-1})=F(b^x)$ ，即 $F(b^x)=a^{x}F(1)$ ，我们得到：
$T_2(x)=a^xF(1)+aT_2(x-1)$
特征方程为 $\lambda^2-a\lambda=0$ ，特征根为 $\lambda_1=0,\lambda_2=a$
设特征方程为 $T_2(x)=c_1a^x+c_2xa^x$ ，带入特解 $T_2(0)=0,T_2(1)=aF(1)$
得到： $c_1=0,c_2=F(1)$
所以：
$T_2(x)=F(1)a^xx$
即：
$T(n)=O(F(1)a^{log_bn}\log_bn)=O(F(1)n^{\frac{1}{\log_ab}}\log_bn)$

首先要求 $F (n)$ 是多项式函数。这样就有常数 $c$ ：
$c=\frac{aF(n/b)-F(n)}{F(n)}$
若 $c\ne 0$ ，则
$\begin{aligned} T(n)&=O\Big( n^{\cfrac{1}{\log_ab}}\times (O(1)+F(b)/c)+\frac{(F(n))^2}{F(n)-aF(n/b)}\Big) \end{aligned}$
若 $c = 0$ ，则
$T(n)=O(F(1)n^{\frac{1}{\log_ab}}\log_bn)$