时间复杂度

参考：时间复杂度

　　时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势。

　　在数学上，时间复杂度被定义为函数渐进上界，可以简单理解为能够反应函数的增长趋势的函数。

　　通常用大O符号表示：$O(f(n))$。其中 $f(n)$ 就是我们计算时间复杂度时的结果。

　　计算 $ f(n) $ 的实质是计算操作的数量。

计算操作数量

　　计算技巧：

忽略常数项
省略系数
循环嵌套时，使用乘法
只取高阶项

常见类型

常数阶$O(1)$

　　常数阶的操作数量与输入数据大小 n 无关，即不随着 n 的变化而变化。

　　在以下函数中，尽管操作数量 size 可能很大，但由于其与输入数据大小 n 无关，因此时间复杂度仍为 $O(1)$：

1
/* 常数阶 */
2
int constant(int n) {
3
    int count = 0;
4
    int size = 100000;
5
    for (int i = 0; i < size; i++)
6
        count++;
7
    return count;
8
}

线性阶$O(n)$

　　线性阶的操作数量相对于输入数据大小 n 以线性级别增长。线性阶通常出现在单层循环中：

1
/* 线性阶 */
2
int linear(int n) {
3
    int count = 0;
4
    for (int i = 0; i < n; i++)
5
        count++;
6
    return count;
7
}

　　实际上就是操作的数量以数据规模 n 的线性级别增长。

　　遍历数组和遍历链表等操作的时间复杂度均为 $O(n)$ ，其中 n 为数组或链表的长度：

1
/* 线性阶（遍历数组） */
2
int arrayTraversal(vector<int> &nums) {
3
    int count = 0;
4
    // 循环次数与数组长度成正比
5
    for (int num : nums) {
6
        count++;
7
    }
8
    return count;
9
}

平方阶 $O(n^2)$

　　平方阶的操作数量相对于输入数据大小 n 以平方级别增长。平方阶通常出现在嵌套循环中，外层循环和内层循环的时间复杂度都为 $O(n)$，因此总体的时间复杂度为 $O(n^2)$ ：

1
/* 平方阶 */
2
int quadratic(int n) {
3
    int count = 0;
4
    // 循环次数与数据大小 n 成平方关系
5
    for (int i = 0; i < n; i++) {
6
        for (int j = 0; j < n; j++) {
7
            count++;
8
        }
9
    }
10
    return count;
11
}

　　以冒泡排序为例，外层循环执行 n−1 次，内层循环执行 n−1、n−2、…、2、1 次，因此时间复杂度为 $O((n−1)*n/2)=O(n^2)$（求和公式）：

1
/* 平方阶（冒泡排序） */
2
int bubbleSort(vector<int> &nums) {
3
    int count = 0; // 计数器
4
    // 外循环：未排序区间为 [0, i]
5
    for (int i = nums.size() - 1; i > 0; i--) {
6
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
7
        for (int j = 0; j < i; j++) {
8
            if (nums[j] > nums[j + 1]) {
9
                // 交换 nums[j] 与 nums[j + 1]
10
                int tmp = nums[j];
11
                nums[j] = nums[j + 1];
12
                nums[j + 1] = tmp;
13
                count += 3; // 元素交换包含 3 个单元操作
14
            }
15
        }
3 collapsed lines
16
    }
17
    return count;
18
}

指数阶 $O(2^n)$

　　生物学的“细胞分裂”是指数阶增长的典型例子：初始状态为 1 个细胞，分裂一轮后变为 2 个，分裂两轮后变为 4 个，以此类推，分裂 n 轮后有 $2^n$ 个细胞。

　　图 2-11 和以下代码模拟了细胞分裂的过程，时间复杂度为 $O(2^n)$ ：

1
/* 指数阶（循环实现） */
2
int exponential(int n) {
3
    int count = 0, base = 1;
4
    // 细胞每轮一分为二，形成数列 1, 2, 4, 8, ..., 2^(n-1)
5
    for (int i = 0; i < n; i++) {
6
        for (int j = 0; j < base; j++) {
7
            count++;
8
        }
9
        base *= 2;
10
    }
11
    // count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1
12
    return count;
13
}

　　在实际算法中，指数阶常出现于递归函数中。例如在以下代码中，其递归地一分为二，经过 n 次分裂后停止：

1
/* 指数阶（递归实现） */
2
int expRecur(int n) {
3
    if (n == 1)
4
        return 1;
5
    return expRecur(n - 1) + expRecur(n - 1) + 1;
6
}

　　指数阶增长非常迅速，在穷举法（暴力搜索、回溯等）中比较常见。对于数据规模较大的问题，指数阶是不可接受的，通常需要使用动态规划或贪心算法等来解决。

对数阶 $O(log⁡\ n)$

　　与指数阶相反，对数阶反映了“每次操作缩减到一半”的情况。设输入数据大小为 n ，由于每次操作都缩减数据规模到一半，数据规模将迅速较少，循环次数是 $log_2\ ⁡n$，即 $2^n$ 的反函数。

　　图 2-12 和以下代码模拟了“每轮缩减到一半”的过程，时间复杂度为 $O(log2 ⁡n)$，简记为 $O(log\ ⁡n)$ ：

1
/* 对数阶（循环实现） */
2
int logarithmic(int n) {
3
    int count = 0;
4
    while (n > 1) {
5
        n = n / 2;
6
        count++;
7
    }
8
    return count;
9
}

　　每一次操作都使 $n=n/2$，这就会快速减少操作的次数。

　　和指数阶一样，对数阶也经常出现在递归函数中，两者的区别在递归返回时调用递归函数时的参数以及调用次数。

1
/* 对数阶（递归实现） */
2
int logRecur(int n) {
3
    if (n <= 1)
4
        return 0;
5
    return logRecur(n / 2) + 1;
6
}

线性对数阶$O(n log n)$

　　线性对数阶常出现于嵌套循环中，两层循环的时间复杂度分别为 O(log⁡n) 和 O(n) 。相关代码如下：

1
/* 线性对数阶 */
2
int linearLogRecur(int n) {
3
    if (n <= 1)
4
        return 1;
5
    int count = linearLogRecur(n / 2) + linearLogRecur(n / 2);
6
    for (int i = 0; i < n; i++) {
7
        count++;
8
    }
9
    return count;
10
}

阶乘阶$O(n!)$

　　阶乘阶对应数学上的“全排列”问题。给定 n 个互不重复的元素，求其所有可能的排列方案，方案数量为：

　　$n!=n\times(n-1)\times(n-2)\times…\times2\times1$

　　阶乘通常使用递归实现。如图 2-14 和以下代码所示，第一层分裂出 n 个，第二层分裂出 n−1 个，以此类推，直至第 n 层时停止分裂：

1
/* 阶乘阶（递归实现） */
2
int factorialRecur(int n) {
3
    if (n == 0)
4
        return 1;
5
    int count = 0;
6
    // 从 1 个分裂出 n 个
7
    for (int i = 0; i < n; i++) {
8
        count += factorialRecur(n - 1);
9
    }
10
    return count;
11
}

　　像回溯算法就属于这一类，由于必须要遍历所有的情况，只能通过递归来实现。

　　请注意，因为当 n≥4 时恒有 n!>2n ，所以阶乘阶比指数阶增长得更快，在 n 较大时也是不可接受的。

　　‍