biscuitの博客

时间代价函数#

时间复杂性分析的目标是将算法的时间代价表示为一个函数 $f(N)$（有的也记作 $T(N)$），其中 $N$ 代表输入规模（输入规模不是数值的大小，而是存储输入需要的位数），用基本语句的次数（而非对应操作的具体时间）来衡量时间复杂性。

以上面这个代码为例，算一下 $f(N)$

忽略基本语句对应操作的时间 $t_i$，用基本语句的执行次数来近似算法的时间代价

进一步，忽略低阶项和常数项，得到$f(N)$的渐近表示，在这里引入大O符号（Big O Notation），表示至多同阶。

渐进表示符号#

渐进表示符号

渐进表示符号其实是一个数学概念，形式化定义如下：

1. 大O符号（Big O Notation）对于给定的函数 $g(n)$ ,用 $\mathbf{O}(g(n))$ 表示函数 $f(n)$ 的集合，并且称 $g(n)$ 是 $f(n)$ 的一个渐进上确界

   $$f(n) = \mathbf{O}(g(n)) \iff \exists c > 0, n_0 > 0, \forall n \geq n_0, 0 \leq f(n) \leq c \cdot g(n)$$

2. 大 $\Omega$ 符号（Big Omega Notation）：对于给定的函数 $g(n)$,用 $\mathbf{O}(g(n))$ 表示函数 $f(n)$ 的集合，并且称 $g(n)$ 是 $f(n)$ 的一个渐进下确界

   $$f(n) = \Omega(g(n)) \iff \exists c > 0, n_0 > 0, \forall n \geq n_0, 0 \leq c \cdot g(n) \leq f(n)$$

3. 大 $\Theta$ 符号（Big Theta Notation）：对于给定的函数 $g(n)$,用 $\mathbf{\Theta}(g(n))$ 表示函数 $f(n)$ 的集合，并且称 $g(n)$ 是 $f(n)$ 的一个渐进紧确界

   $$f(n) = \Theta(g(n)) \iff \exists c_1 > 0, c_2 > 0, n_0 > 0, \forall n \geq n_0, 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$$

4. 小o符号表示 $f(n)$ 的增长率严格小于 $g(n)$

   $$f(n) = o(g(n)) \iff \forall c > 0, \exists n_0 > 0, \forall n \geq n_0, 0 \leq f(n) < c \cdot g(n)$$

5. 小 $\omega$ 符号表示 $f(n)$ 的增长率严格大于 $g(n)$

   $$f(n) = \omega(g(n)) \iff \forall c > 0, \exists n_0 > 0, \forall n \geq n_0, 0 \leq c \cdot g(n) < f(n)$$

• 这里的等号不是严格的数学等号，而是类似 $\in$ 的一种符号
• 这里面的常数 $c, c_1, c_2$ 和 $n_0$ 都是正数，函数 $f(n)$ 和 $g(n)$ 都是非负函数（严格来说叫渐进非负，就是当n足够大时满足非负）
• 确定常数 $c, c_1, c_2$ 和 $n_0$ 的的过程依赖于具体的函数 $f(n)$ 和 $g(n)$
• 小o符号和小 $\omega$ 符号，表示严格小于和严格大于，注意这两个定义中 $g(n)$ 的倍数因子 $c$ 满足任意性：

在算法分析中，常用以下三种符号来表示代价函数在输入规模达到一定程度后渐近增长行为：

1. 大O符号（至多同阶），若m次多项式 $A(n)=a_mn^m+a_{m-1}n^{m-1}+\dotsb+a_1n+a_0$ ,则 $A(n)=\mathbf{O}(n^m)$

   • 忽略低阶项和常数项，关注输入规模 $N$ 增长
   • 可以把 $\mathbf{O}(N^n)$ 理解成阶数不超过n的函数族或多项式集合
   • $O(n^m)$ 描述代价函数的最坏情况，阶数越低代价函数增长的上界越精确

2. 大 $\Omega$ 符号（至少同阶），若m次多项式 $A(n)=a_mn^m+a_{m-1}n^{m-1}+\dotsb+a_1n+a_0$ ,则 $A(n)=\mathbf{\Omega}(n^m)$

   • $\Omega(n^m)$ 描述代价函数阶数的最好情况，阶数越高代价函数增长下界越精确

3. 大 $\Theta$ 符号（同阶），若m次多项式 $A(n)=a_mn^m+a_{m-1}n^{m-1}+\dotsb+a_1n+a_0$ ,则 $A(n)=\mathbf{\Theta}(n^m)$

   • 这里的等号类似 $\in$，把 $\mathbf{\Theta}(N^n)$ 理解成阶数等于n的函数族或多项式集合
   • $\Theta(n^m)$ 表示代价函数的增长率与 $c_0n^m\sim c_1n^m$ 一样快
   • 如果 $f(n)=O(g(n))$ 且 $f(n)=\Omega(g(n))$ ，则 $f(n)=\Theta(g(n))$

例题：求冒泡排序的时间复杂度

1
void bubblesort(int arr[], int n) {
2
    for (int i = 0; i < n - 1; i++) {
3
        for (int j = 0; j < n - i - 1; j++) {
4
            if (arr[j] > arr[j + 1]) {
5
                // 交换 arr[j] 和 arr[j+1]
6
                int temp = arr[j];
7
                arr[j] = arr[j + 1];
8
                arr[j + 1] = temp;
9
            }
10
        }
11
    }
12
}

solution

主要是两层嵌套循环，外层i从0到n-2，内层j从0到n-i-2，外层执行n-1次，内层执行

$$(n-1)+(n-2)+\dotsb+1 = \frac{(n-1)n}{2}$$

次，所以时间复杂度为$O(n^2)$

例二：求阶乘的时间复杂度

1
int factorial(int n) {
2
    if (n == 0 || n == 1) {
3
        return 1;
4
    }
5
    return n * factorial(n - 1);
6
}

solution

递归调用n次，所以时间复杂度为 $O(n)$

例三：二分法查找的复杂度

1
int binarySearch(int arr[], int size, int target) {
2
    int left = 0;
3
    int right = size - 1;
4
    while (left <= right) {
5
        int mid = left + (right - left) / 2;
6
        if (arr[mid] == target) {
7
            return mid;
8
        } else if (arr[mid] < target) {
9
            left = mid + 1;
10
        } else {
11
            right = mid - 1;
12
        }
13
    }
14
    return -1;
15
}

solution

每次循环将查找范围缩小一半，假设初始范围为n,经过k次循环后，范围变为 $\frac{n}{2^k}$ ,当范围缩小到1时，停止循环，即 $\frac{n}{2^k}=1$ ,解得 $k=\log_2 n$ ，所以时间复杂度为 $O(\log n)$ 这种“每次操作都将问题规模缩小一半”的算法，复杂度通常都是 $O(\log n)$ 。