数学基础

定义

如果存在正常数c与n₀，使得当N >= n₀时T(N) <= cf(N)，则记为$T(N）= O(f(N))$。

如果存在正常数c与n₀, 使得当N >= n₀时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))$。

法则

如果T₁₍N) = $O(f(N))$且T₂(N) = $O(g(N))$，那么:

(a)T₁(N) + T₂(N) = $max(O(f(N)), O(g(N)))$

(b)T₁(N) * T₂(N) = $O(f(N) * g(N))$

如果T(N)是一个k次多项式，则$T(N) = \Theta(N^k)$

对于任意常数k，$\log^k{N} = O(N)$

函数增长率

典型增长率

判断两个函数的增长率

可以通过比较两个函数的极限:$\lim\limits_{n \to \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}) + N\log{N}$

其中a = 3，b = 4，f(N) = $N\log{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})\log\frac{N}{4} \leq \frac{3}{4}N\log{N} = cf(N)$，其中$c = \frac{3}{4}$。这就满足了情形3，即$T(N) = \Theta(N\log{N})$。

4 $T(N) = 2T(\frac{N}{2}) + N\log{N}$

其中a = 2，b = 2，$f(N) = N\log{N}$, $N^{\log_{b}{a}} = N^{\log_{2}{2}} = N$，表面上看，这属于情形3，但是，却不存在一个正常数$\varepsilon$，使得$\frac{f(N)}{N^{\log_{b}{a} + \varepsilon}} = \frac{N\log{N}}{N^{\log_{2}{2} + \varepsilon}} = \frac{N\log{N}}{N * N^\varepsilon} = \frac{\log{N}}{N^\varepsilon} \ge 1$。所以无法运用上面3中情形的公式。