数学基础
定义
如果存在正常数c与n0，使得当N >= n0时T(N) <= cf(N)，则记为$T(N）= O(f(N))$。
如果存在正常数c与n0, 使得当N >= n0时T(N) >= cg(N)，则记为$T(N) = Omega(g(N))$。
当且仅当T(N) = O(h(N))且T(N) = Ω(h(N))时，则$T(N) = Theta(h(N))$。
如果T(N) = O(p(N))且T(N) != Θ(p(N))，则$T(N) = o(p(N))$。
法则
如果T1(N) = $O(f(N))$且T2(N) = $O(g(N))$，那么:
(a)T1(N) + T2(N) = $max(O(f(N)), O(g(N)))$
(b)T1(N) * T2(N) = $O(f(N) * g(N))$
如果T(N)是一个k次多项式，则$T(N) = Theta(N^k)$
对于任意常数k，$log^k{N} = O(N)$
函数增长率
典型增长率
| 函数 | 名称 |
| c | 常数 |
| $log{N}$ | 对数级 |
| $log^2{N}$ | 对数平方根 |
| N | 线性级 |
| $Nlog{N}$ | |
| $N^2$ | 平方级 |
| $N^3$ | 立方级 |
| $2^N$ | 指数级 |
判断两个函数的增长率
可以通过比较两个函数的极限:$limlimits_{n o infty}frac{f(N)}{g(N)}$，来确定两个函数的增长率。必要的时候，还可以使用洛必达法则。
该极限有4种可能:
1 极限是0，这意味着$f(N) = o(g(N))$;
2 极限是常数c != 0，这意味着$f(N) = Theta(g(N))$;
3 极限是$infty$，这意味着$g(N) = o(f(N))$;
4 极限摆动，二者无关
运行时间计算的一般法则
for循环
一次for循环的运行时间至多是for循环内语句(包括测试)的运行时间乘以迭代得次数
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
k++;
}
}
上面的例子当中，时间复杂度是$N^2$。
顺序语句
将各个语句的运行时间求和即可(这意味着，其中的最大值就是所得得运行时间)
for (i = 0; i < N; i++) {
A[i] = 0;
}
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
A[i] += A[j] + i + j;
}
}
上面例子当中，第一个循环时间复杂度是$O(N)$，第二个循环时间复杂度是$O(N^2)$，两个循环的总体时间复杂度为$O(N) + O(N^2) = max(O(N), O(N^2))$，也就是还是$O(N^2)$。
if/else语句
对于程序片段:
if (condition) {
S1;
} else {
S2;
}
一个if/else语句得运行时间从不超过判断再加上S1和S2中运行时间长的运行时间。
运行时间中的对数
如果一个算法用常数时间O(1)将问题的大小削减为其一部分(通常是1/2)，那么该算法得时间复杂度就是$O(log{N})$。举个例子，下面是用迭代的方法写的二分查找：
int BinarySearch(const ElementType A[], ElementType X, int N) {
int Low, Mid, High;
Low = 0;
High = N - 1;
while (Low <= High) {
Mid = (Low + High) / 2;
if (A[Mid] < X) {
Low = Mid + 1;
} else {
if (A[Mid] > X) {
High = Mid - 1;
} else {
return Mid;
}
}
}
return NotFound;
}
在上面的二分法中，每次迭代的时间复杂度是$O(1)$，并且每次迭代之后，问题复杂度就减为原来的一半，因此，这个程序的时间复杂度为$O(log{N})$。
另一方面，如果使用常数时间只是把问题减少一个常数(如将问题减少1)，那么这种算法就是$O(N)$。举个例子，下面使用递归的方式求解N!:
long int Factorial(int N) {
if (N <= 1) {
return 1;
} else {
return N * Factorial(N - 1);
}
}
在上面的递归中，每次递归的时间复杂度是$O(1)$，并且递归之后，问题复杂度只比原来少1，因此，这个程序的时间复杂度就是$O(N)$。
递归时间复杂度总结
对于一个问题复杂度为T(N)的问题，可以分解为如下的表达式:
$T(N) = aT(frac{N}{b}) + f(N)$，其中a是常数，且a >= 1, b也是常数，b > 1。
1 如果存在正常数$varepsilon > 0$令$f(N) = O(N^{log_{b}{a} - varepsilon})$，那么$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 如果存在正常数$varepsilon > 0$使得$f(n) = Omega(N^{{log_{b}{a}} + epsilon})$且存在常数c < 1使得对于足够大的N满足$af(frac{N}{b}) leq cf(N)$，那么$T(N) = Theta(f(N))$.
这三种情形如何记忆呢？我们可以这样记忆，三种情况的结果取决于函数f(N)与$N^{log_{b}^{a}}$的大小。如果$N^{log_{b}^{a}}$大，那么结果就是情形1；如果是f(N)大，那么结果就是情形3；如果两个同级别，那么就是情形2。
还需要注意的事情是，这三种情形没有覆盖所有的情形。情形1与情形2之间有Gap，如果f(N)比$N^{log_{b}{a}}$小，但是如果不是同时小一个$N^epsilon$因子，就落到情形1与情形2之间；同时，情形2与情形3之间也有Gap，如果f(N)比$N^{log_{b}{a}}$大，但是如果不同时大一个$N^epsilon$因子，就落到情形2与情形3之间。如果发生这两种情形，就无法应用上面的三个公式。
下面我们看一下实际的例子。
1 $T(N) = 9T(frac{N}{3}) + N$
其中a = 9, b = 3, f(N) = N，$N^{log_{b}{a} } = N^{log_{3}{9}} = Theta(N^2)$，并且$f(N) = O(N^{log_{3}{9 - varepsilon}})$，其中$varepsilon = 1$，那么这个满足情形1，即$T(N) = Theta(N^{log_{3}{9}}) = Theta(N^2)$。
2 $T(N) = T(frac{2}{3}N) + 1$
其中a = 1，b = $frac{3}{2}$，f(N) = 1，同时$N^{log_frac{3}{2}{1}} = N^0 = 1$，那么这就满足情形2，即$T(N) = Theta(N^{log_frac{3}{2}{1}}log{N}) = Theta(log{N})$。这其实就是上面运行时间中的对数当中得情形1。
3 $T(N) = 3T(frac{N}{4}) + Nlog{N}$
其中a = 3，b = 4，f(N) = $Nlog{N}$，$N^{log_{b}{a}} = N^{log_{4}{3}} = Omega(N^{0.793})$。因为$f(N) = Omega(N^{log_{4}{3} + varepsilon})$ $varepsilon cong 0.2$，同时对于足够大的N，满足$af(frac{N}{b}) = 3(frac{N}{4})logfrac{N}{4} leq frac{3}{4}Nlog{N} = cf(N)$，其中$c = frac{3}{4}$。这就满足了情形3，即$T(N) = Theta(Nlog{N})$。
4 $T(N) = 2T(frac{N}{2}) + Nlog{N}$
其中a = 2，b = 2，$f(N) = Nlog{N}$, $N^{log_{b}{a}} = N^{log_{2}{2}} = N$，表面上看，这属于情形3，但是，却不存在一个正常数$varepsilon$，使得$frac{f(N)}{N^{log_{b}{a} + varepsilon}} = frac{Nlog{N}}{N^{log_{2}{2} + varepsilon}} = frac{Nlog{N}}{N * N^varepsilon} = frac{log{N}}{N^varepsilon} ge 1$。所以无法运用上面3中情形的公式。