

Copyright

本页面贡献者：水之幡米拉。本页面内容遵循 MIT 协议，转载请附上原文出处链接和本声明。

时间复杂度¶

我们为什么需要计算时间复杂度¶

现代计算机每秒可以处理数亿乃至更多次基本运算，因此我们处理的数据规模通常很大。但如果计算的量很大，那么计算量可能会是个天文数字，那么即便是超级计算机，也需要耗费极大的时间去解决。

比如，假设数据量为 $n$ (可以理解为有 $n$ 个数需要进行处理)，算法 $A$ 的计算量为 $2^n$ ，而算法 $B$ 的所需计算量为 $n^2$ 。假设超级计算机每秒可进行 $10^{12}$ 次计算。如果 $n\le 80$ ，那么计算机都可以在极短时间内计算出结果，但如果 $n$ 很大，比如 $n = 10^5$ ，那么显然，计算机无法在短时内计算完算法 $A$ 。

如何计算时间复杂度¶

首先我们需要了解几个概念 基本操作数, $T(n),O(n)$

基本操作数¶

在普通的计算机上，加减乘除、访问变量（基本数据类型的变量）、给变量赋值等都可以看作基本操作。比如:

int x, y;
scanf("%d%d", &x， &y);
int z = x - y;
if(z == 0)
    printf("233\n");

函数 $T$ ¶

当数据规模为 $n$ 时, $T(n)$ 表示算法所需的计算量在此过程中，基本操作算作一次运算

比如这个程序：

int ans = 0;
for(int i = 1; i <= n; ++i) {
    ans += i;
    printf("%d ", ans);
}

在单次循环中，执行了四次个基本操作:

ans += i;
printf("%d ", ans);
++i
if(i <= n)

一共循环了

$n$ 次，那么 T(n) = 4 * n 准确的说，还有这三个地方没有计算

int i = 1;
++i; //当i=100时
if(i <= n) //当i=101时

所以，最终结果应该是

$T(n) = 4 * n + 3$

渐进符号 $O$ ¶

定义:对于两个函数, $f(n),g(n)$ 设 $f(n) = O(g(n))$ ，则有: $\exists c \in R^*, n_0 \in N^*$ ，使得 $\forall n \ge n_0$ ,有 $0 \le f(n) \le c * g(n)$ 。

~~人话版本~~ 当 $n$ 很大的时候， $f(n)$ 始终小于等于 $g(n)$ 乘上一个常数 $c$ 。

如何计算 $O$ ¶

对于 $T(n) = 4 * n + 3$ ,那么 $O(T(n)) = n$ 为什么呢？因为 $n \ge 1时$ ， $4 * n + 3 <= 5 * n$ 此时， $c = 5, n_0 = 1$

那么对于 $T(n) = 3*n^2 + 100 * n + 114514$ ， $O(T(n))$ 是多少呢？

实际上对于 $T(n) = 3*n^2 + 100 * n + 114514$ $O(T(n)) = n^2$

为什么呢？因为当 $n$ 足够大的时候， $n^2$ 的增长速度会远超 $100 * n$ ，其大小也会远超 $114514$ ,所以我们只需要找到 $n^2$ 的上限即可，此时那么显然 $4 * n ^ 2$ 可以满足。(当然 $3.01 * n ^ 2$ 也可以，只要 $n$ 足够大)

综上，只要我们知道 $T(n)$ 的表达式，那么我们只需找到它在数据范围为 $n$ 时,增长最快的一项即可。实际上，我们也不需要完整的求出 $T(n)$ ，因为我们只关注它增长速度最大的那一项。

所谓的 $O()$ 就是我们平时所说时间复杂度。

比如当 $n <= 10^5$ 时，对于 $T(n) = 100 * n^2 + 114514 * n + n! + log_2(n)$ 那么显然有: $O(T(n)) = n!$ 记为 $O(n!)$

计算时间复杂度时需要注意的细节¶

那么它们的时间复杂度显然都是 $O(n)$ ，但是这两个算法在运行时，所消耗时间肯定有很大区别，因为在 $T(n)$ 的表达式中，算法 $A$ 中 $n$ 的前面乘上了一个很大的常数,它的大小甚至大于了 $n$ 的范围，所以此时，虽然它是个常数，但它对计算量的大小影响是十分显著的，我们需要考虑它的影响。

$O的定义是$ : $\exists c \in R^*, n_0 \in N^*$ ，使得 $\forall n \ge n_0$ ,有 $0 \le f(n) \le c * g(n)$ 。这个 $c$ 其实就是我们刚才说的常数。

通常情况下，基本操作对时间复杂度的影响我们是可以不考虑的，除非我们在一个循环，或者递归中，加入了很多次的运算。

简单来说，只要 $c \le 50$ ，那么通常来说,问题不大(更严谨的来说，要根据 $n$ 的范围)。

通过时间复杂度，我们可以判断出我们程序是否可以在规定时间内运行完。

一般来说，比赛的评测姬一秒能执行 $5 * 10 ^ 8$ 次左右的运算，精确数值通常无从所知。

所以,对于 $n \le 2 * 10 ^ 4$ 的数据量， $O(n^2)$ 就是极限了，此时常数过大就有可能 $TLE$ 。

计算时间复杂度 - 循环¶

for(int i = 1; i <= n; ++i)
    printf("ldstql!\n");
for(int j = 1; j <= m; ++j)
    printf("zhrtql!\n");

分析： 两个循环分别执行了

$n$ 次和

$m$ 次，所以时间复杂度为

$O(n + m)$

for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= m; ++j)
        printf("ldstql!\n");

分析： 外层循环执行了

$n$ 次，每个外层循环中，有一个

$m$ 次循环，所以时间复杂度为

$O(n*m)$

for(int i = 1; i <= n; ++i)
    for(int j = i + 1; j <= n; ++j)
        printf("ldstql!\n");

分析: 计算次数

$sum = \sum_{i = 1}^{n - 1} = 1 + 2 + 3 + ... + n - 1 = \frac{n * (n - 1)}{2} = \frac{1}{2}(n ^ 2 - n)$ 所以时间复杂度仍然是

$O(n^2)$

for(int i = 1, j = 1; i <= n; ++i) {
    for(; j <= i; ++j)
        printf("ldstql!\n");
}

分析: 虽然仍然是两层循环，但是在每一次外层循环中，

$j$ 并没有遍历到

$n$ ,即, $i,j$ 只会增加，不会减少。对于这种情况，方便算法是计算他们的起点和终点,那么

$sum = n + n$ ,所以时间复杂度为

$O(n)$

计算时间复杂度 - 位运算¶

while(n) {
    printf("ldstql!\n");
    n >>= 1;
}

分析: 本质上是

$n$ 二进制下有多少位，那么

$for$ 循环就会执行几次，比如

$9_{(10)} = 1001_{(2)}$ 吗,那么显然它会执行

$4$ 次。

那么我们怎么才能得出它二进制下有多少位呢？其实很简单 $sum = log_{2}(n)$ 那么它的时间复杂度就是 $O(log_2(n))$ 。

由于在算法竞赛中，时间复杂度如果有对数的,那么基本都是以 $2$ 为底数的，所以默认情况下 $log(n)$ ，就是以 $2$ 为底数的。

计算时间复杂度 - 递归¶

void dfs(int x)
{
    if(x == n)
        return ;
    dfs(x + 1);
    for(int i = 1; i <= x; ++i)
        printf("ldstql ");
    printf("\n");        
}
dfs(1);

分析: 递归深度是

$n$ ,在每层递归程序中,有个执行

$x$ 次的循环，那么实际上它的时间复杂度与之前的二层循环是一样的，即

$O(n^2)$

void dfs(int l, int r)
{
    if(l == r) {
        printf("ldstql!\n");
        return ;
    }
    int mid = (l + r) >> 1;
    dfs(l, mid);
    dfs(mid + 1, r);
}

dfs(1, n);

我们用 $[l, r1]$ 来表示每次递归的范围,并假设 $n = 8$

第 $0$ 次递归: $[1, 8]$ 第 $1$ 次递归: $[1, 4]$ , $[5, 8]$ 第 $2$ 次递归: $[1, 2]$ , $[3, 4]$ , $[5, 6]$ , $[7, 8]$ 第 $3$ 次递归: $[1, 1], [2, 2], [3,3], [4,4],[5,5],[6,6],[7,7],[8,8]$

显然，它的递归边界范围( $r - l + 1$ )在每次递归中都会一分为二，所以递归深度为 $\lceil log_2(n) \rceil$ 。在第 $i$ 层递归中,共有 $2^i$ 个分支。那么总次数 $sum = \sum_{i = 0}^{\lceil log_2(n) \rceil} 2^i = 2^{\lceil log_2(n) \rceil + 1} - 1 = 2 * n - 1$ 所以时间复杂度为 $O(n)$