复杂度分析

算法入门中,我们已经基本了解了算法的定义,下面我会对如何衡量算法的性能进行更深入地讨论。

1 事前分析

一个算法的性能到底如何,直接执行一下,统计性能数据不就行了嘛!很多情况下,「事后统计」似乎是一个显而易见的答案。

但很多情况下我们无法做这样的的统计,比如我们要对导弹上的算法进行性能测试,一颗导弹的价格可能就高大几十万甚至上亿,导弹上有很多解决不同问题的算法,如果每种算法都要实际测试,会消耗掉大量的资源!

其次,对于每个问题,我们可能先要尝试一些简单的算法,然后逐步去找到最适合的算法。如果不能先对算法进行「事前分析」,那么研发成本将无法接受。

尽管上面的例子有些极端,但如果我们可以很快的分析出 A 算法的性能比 B 算法的性能好,那么我们就无需真正的去执行 B 算法,就直接排除它。快速的排除较差的算法可以节省不少计算资源和时间,从而更快地找到解决问题的最优算法。

2 大 O 表示法

如果真正的比较两个算法的实际性能,可能会是一件比较复杂的问题。比如 A 算法的执行次数是 $2n+3$,B 算法的执行次数是 $n^2 + n + 10$,当 $n \to \infty$ 时,A 算法的主要由 $2n$ 决定,B 算法主要由 $n^2$ 决定,我们只要比较它们的主体部分就可以确定它们的大小关系。

大 O 表示法 是将它们主体的常数项也去掉,然后用 O 和括号包起来,A B 算法分别表示为 $O(n)$ 和 $O(n^2)$,这样我们就更清晰的比较它们。

常见渐近复杂度比较如下:

$$ O(1) < O(log_2{n}) < O(n) < O(nlog_2{n}) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n) $$

3 复杂度分析

通常来说,一个好的算法一定是「即快又省」的!快是指它运行的速度快,省是指它占用的存储空间小。

我们通过对时间复杂度和空间复杂度的综合分析,来评判一个算法的好坏!

3.1 时间复杂度

这里的时间是指程序在 CPU 上的运行时间,在没有实际运行的情况下,我们很难估算出这个时间,因此我们用 单次运行时间 * 运行次数 来近似表示,我们又假设单次运行的平均时间是相同的,所以仅仅可以通过估算代码的运行次数估算出大概的运行时间。

1
2
3
4
5
n = 10
j = 0
for i in range(n):
j = i + j
print(j)

我们看上面这段 Python 代码,它的运行次数为 $2+10+1=13$,它用大 O 表示法为 $O(n)$。

3.2 空间复杂度

空间复杂度即是算法在运行中所需要的空间大小。如果原地工作,不使用额外的空间,那么算法的空间复杂度就是 $O(1)$;如果算法需要额外使用与数据长度成简单正比关系,那么空间复杂度就是 $O(n)$。

1
2
3
4
5
6
7
n = 10
j = 0
sum_list = []
for i in range(n):
j = i + j
sum_list.append(j)
print(sum_list)

假设我们需要保存每一步 j 的值,就需要一个大小为 n 的数组,所占空间即为 n,它用大 O 表示法为 $O(n)$。

学会了时间复杂度和空间复杂度,就可以对算法进行事前预估!快去找一些算法试着分析一下吧~

4 参考

作者

Ailln

发布于

2018-11-01

更新于

2024-03-02

许可协议

评论