复杂度分析讲义

简介

在评估一个算法的效率时，重点关注的是算法的时间复杂度与空间复杂度。

其中，因为不同机器的性能不同，所以在评测算法的时间复杂度时，并不是去评测实际的用时，而是算法执行完需要进行的基本操作的数量。

时间复杂度

定义

在评判一个算法的快慢时，一定要考虑数据规模，即输入的数字个数、给定字符串的长度等等。一般来说，数据规模越大，算法的用时就越长。

当然，在算法竞赛中，衡量一个算法的效率时，最重要的不是看它在某个数据规模下的用时，而是看它的用时随数据规模而增长的趋势，即 时间复杂度，也称 渐进时间复杂度。

当然，时间复杂度并非完全由数据规模决定，也和其中输入的内容有关，例如我们写了一个从头到尾查找指定数字的算法，可能这个数字在第一个，一次就找到了；也可能它在最后，要找完所有数字才能找到，所以，在描述时间复杂度时，一般又分为几种，例如：

• 最坏时间复杂度，即每个输入规模下用时最长的输入对应的时间复杂度。在算法竞赛中，一般都是考虑最坏时间复杂度。（是的，善良的出题人一定会出这种数据）
• 平均（期望）时间复杂度，即每个输入规模下所有可能输入对应用时的平均值的复杂度。

计算

算法的时间复杂度通常用大 $O$ 符号表示 ，算法的准确复杂度用 $T[n]$ 表示，如果有某个辅助函数 $f(n)$，存在一个正常数 $c$ 使得 $f(n)\times c>=T[n]$ 恒成立，则记作 $T[n]=O(f(n))$ ，在描述 $f(n)$ 这个函数时，为了方便计算，一般只记录最高次项，忽略其他项和常数。

常见的时间复杂度：

• 常数阶 $O(1)$
• 对数阶 $O({\log }_{2}n)$
• 平方根阶 $O(\sqrt{n})$
• 线性阶 $O(n)$
• 线性对数阶 $O(nlo{g}_{2}n)$
• 平方阶 $O(n^2)$
• 立方阶 $O(n^3)$
• K次方阶 $O(n^k)$
• 指数阶 $O(2^n)$
• 阶乘阶 $O(n!)$

在算法竞赛的测评机上，一般 $1$ 秒时间可以执行 ${10}^8$ 次指令，可以以此为标准来估算程序是否会超时。

样例

$O(1)$ 常数阶

int a, b;
cin >> a >> b;
cout << a+b;

这就是常量级的代码，并不是说只执行一行代码，而是不管输入的数据有多大，执行的都是这几次操作，那么就是常量阶。

$O({\log }_{2}n)$ 对数阶

int a;
cin >> a;
while (a > 0) {
    cout << a%2;
    a /= 2;
}

可以计算一下，当 $a=16$ 时，循环会执行 $5$ 次；当 $a=1024$ 时，循环会执行 $11$ 次，这个增长速度就是对数阶的增长速度。

对数的概念：如果 $N=a^x(a>0,a\ne 1)$，即 $a$ 的 $x$ 次方等于 $N$，并且 $a>0,a\ne 1$，那么数 $x$ 叫做以 $a$ 为底的 $N$ 的对数，记作 $x={\log }_{a}N$，其中 $a$ 是对数的底数，$N$ 叫做真数，$x$ 叫做 以 $a$ 为底 $N$ 的对数 。

一般来说，对数简写为 $\log N$ 时，相当于 ${\log }_{2}N$ 。

$O(\sqrt{n})$ 平方根阶

int n;
cin >> n;
for (int i=2; i<=n/i; i++) {
	if (n%i == 0) {
		cout << "不是质数";
        return 0;
    }
}
cout << "是质数"

上面演示的判断质数的方法，其循环的次数就是 $O(\sqrt{n})$ 。

平方根的概念：如果 $x^2=n$，那么 $\sqrt{n}=x$。

而在时间复杂度表示中，$\sqrt{n}$ 一般指算术平方根，即非负数的平方根。

$O(n)$ 线性阶

int n, sum=0;
cin >> n;
for (int i=1; i<=n*2; i++) {
	sum += i;
}

上面算法的实际运行是 $2\times n$，但是在表示时会省略常数，所以是 $O(n)$ 级别的算法。

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

int n;
cin >> n;
for (int i=1; i<=n; i++) {
    int cnt = 0, x = i;
    while (x) {
        cnt++;
        x /= 2;
    }
    cout << cnt << " ";
}

上面代码有两层循环，外层循环为 $n$ 次，内层循环每次都是 $\log i$，因为 $i$ 的上界是 $n$，所以内层循环可以视为 $\log n$，总时间复杂度是 $O(n\log (n))$ 。

$O(n^2)$ 平方阶

int n, cnt=0;
cin >> n;
for (int i=1; i<=n; i++) {
    for (int j=1; j<=n; j++) {
        if (i+j == 10) cnt++;
    }
}
cout << cnt;

嵌套循环的时间复杂度计算为乘法，上述代码的时间复杂度是 $O(n^2)$ 。

平方的概念：$n^2$ 等同于 $n\times n$ 。

$O(n^3)$ 立方阶

int n, cnt=0;
cin >> n;
for (int i=1; i<=n; i++) {
    for (int j=1; j<=n; j++) {
        for (int k=1; k<=n; k++) {
            if (i+j+k == 15) cnt++;
		}
    }
}
cout << cnt;

类似于平方阶的计算，时间复杂度为 $O(n^3)$ 。

立方的概念：$n^3$ 等同于 $n\times n\times n$ 。

$O(n^k)$ k次方阶

int sum = 0;

void dfs(int k) {
    if (k == 0) return ;
    for (int i=1; i<=n; i++) {
        sum += i;
    }
    dfs(k-1);
}

上述代码演示了一个 $O(n^k)$ 级别的递归函数，如果还没学习递归的同学，可以学习了递归之后再回过头来看。

次方的概念：$n^k$ 相当于 $k$ 个 $n$ 相乘，即 $n\times n\times n\cdots \times n$ 。

$O(2^n)$ 指数阶

int dfs(int n) {
    if (n == 0 or n == 1) return 1;
    return dfs(n-1) + dfs(n-2);
}

上述代码演示了一个 $O(2^n)$ 级别的递归函数，如果还没学习递归的同学，可以学习了递归之后再回过头来看。

这个算式相当于 $n$ 个 $2$ 相乘。

$O(n!)$ 阶乘级

int dfs(int n) {
    if (n == 0) return 1;
    for (int i=1; i<=n-1; i++) {
    	dfs(i);
    }
}

上述代码演示了一个 $O(n!)$ 级别的递归函数，如果还没学习递归的同学，可以学习了递归之后再回过头来看。

阶乘的概念：$n!=1\times 2\times 3...\times n$ 。

常见数据规模与时间复杂度的适用关系

空间复杂度

空间复杂度主要和数组、字符串等容器的大小有关系。

例如，用数组存 $n$ 个数字，那么空间复杂度就是 $S(n)$；用二维数组存 $n\times m$ 个数字，空间复杂度就是 $S(n\times m)$ 。

另外，递归调用函数时同样会使用空间，所以要注意递归的层数以及函数中存储的数据。

假设题目的空间限制为 $128MB$，那么数组的大小极限大概是 $3\times {10}^7$。一般来说数组的大小都不会开到 ${10}^7$ 以上，如果开到这么大，那可能你需要思考一下是否算法设计得不合理。