算法的复杂度分析

算法的复杂度分析

时间,空间复杂度是衡量算法效率的重要指标

为什么要对算法进行复杂度分析?

事后统计法,也就是实际运行代码时,监控、统计代码的运行时间和内存占用的方法,虽然可以得到算法的执行效率数据,但是,这种统计方法存在很大的局限性

  • 测试结果对测试环境依赖极高
  • 测试结果受数据规模影响极大

因此,我们需要一个不用具体的测试数据进行测试,就可以粗略的估算算法的运行效率的方法,这种方法就是时间、空间复杂度分析方法

大O复杂度表示法

算法的执行效率,简单来讲就是程序运行的时间,在不运行代码的情况下,我们如何得到算法的运行时间呢?

以下面一段代码为例,我们估算一下代码的运行时间

1
2
3
4
5
def call(n):
s = 0
for i in range(n):
s = s + i
return s

从处理器运行的角度来看,执行一段代码的每一行时都有类型:读数据、运算、写数据操作。我们假设处理器在执行每一行代码时所需要的时间时一样的 ,设为runtime,在这个假设的基础上,上述代码的运行时间就可以估算了:

第1行代码用时 1个runtime ,第2,3行代码用时 2n个runtime ,第4行代码用时1个runtime ,总共的运行时间

$$
T(n) = 2runtime + 2n * runtime
= 2 * runtime * (n+2)
$$

可以看到所有代码的执行时间与代码执行的次数f(n)成正比

再看看下面的代码:

1
2
3
4
5
6
def call(n):
s = 0
for i in range(n):
for j in range(n):
s = s + (j * i)
return s

代码的运行时间为:

$$
T(n) = (2 + n + 2n * n) * runtime
$$

同样 代码的执行时间与代码执行的次数f(n)成正比

将这个规律总结为公式:

$$
T(n) = O(f(n))
$$

其中T(n)表示代码的运行时间,n表示数据规模的大小,f(n)表示每次执行的次数总和,这就是大O时间复杂度表示法

大O时间复杂度表示法实际并不是表示代码的具体执行时间,而是表示代码运行时间随数据规模增长的变化趋势,也叫做渐进时间复杂度,简称时间复杂度

当n很大的时候,比如10000、100000000,公式中的低阶、常量、系数部分并不能左右增长趋势,所以都可以忽略,我们只需要记住一个最大量级即可。如上述两端代码的复杂度可以表示为$T(n) = O(n) , T(n) = O(n^2)$

时间复杂度分析

如何分析一段代码的时间复杂度?

  • 只关注循环最多的那一段代码
  • 加法法则:总复杂度等于量级最大的那段代码的复杂度
  • 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见的时间复杂度

总体来说复杂度量级可以粗略分为:

  • 多项式量级
    • 常量阶 $O(1)$
    • 对数阶 $O(logn)$
    • 线性阶 $O(n)$
    • 线性对数阶 $O(n · logn)$
    • 平方阶、立方阶、K次方阶 $O(n^2)) , O(n^3) , O(n^k)$
  • 非多项式量级
    • 指数阶 $O(2^n)$
    • 阶乘阶 $O(n!)$

当数据的规模越来越大时,非多项式算法的执行时间会急剧增加,求解时间会无限增长,因此,非多项式算法实际是非常低效的算法。

看看常见的多项式量级复杂度:

  1. 常量阶 $O(1)$

    $O(1)$只是常量级时间复杂度的一种表示方法,并不是只执行了一行代码。只要代码的执行时间不随n的增大而增大,这样代码的复杂度我们都记作$O(1)$ , 一般情况下,只要算法中不存在循环语句、递归语句、即使有成千上万行的代码,其时间复杂度也是$O(1)$

  2. 对数阶 $O(logn) $ $O(n · logn)$

    对数阶时间复杂度非常常见,同时也是最难分析的一种时间复杂度,例如以下代码

    1
    2
    3
    i = 1
    while i<n :
    i = i * 2

    可以看到第2,3行的代码是执行次数最多的,因此计算复杂度我们需要计算出代码执行的次数

    从代码中可以看出,i从1开始取,每次乘2 直到 i大于或等于n,设执行次数为x则 $i = 2^x$ 当 $2^x >= n $时,程序运行结束,因此$x<= log_2n$ 所以这段代码的复杂度为$O(log_2n)$ 由于对数之间是可以转换的 因此不论对数的底数时多少,都省略

    $O(n·logn)$ 实际就是一个执行了n次的 $logn$ 可以理解为 在上述示例代码中又加了一个n次的循环

  1. $ O(m+n) , O(m*n)$

    这种代码的复杂度由m和n两个数据规模决定,由于无法事先决定数据的量级,因此, 评估算法时,不能简单的利用加法省略,原有的加法法则也不再生效 应改为
    $$
    T_1(n) + T_2(m) = O(f(m)+f(n))
    $$

空间复杂度分析

空间复杂度的全称是渐进空间复杂度,表示算法的存储空间与数据规模之间的增长关系

以下面代码为例,分析空间复杂度

1
2
3
4
def call(n):
res = []
for i in range(n):
res.append(i*i)

第二行我们申请了一个list来存储变量,但这是常数阶的,第4行我们最终创建了大小为n的list,其他的地方没有占用存储空间,因此整段代码的空间复杂度为$O(n)$

常见的空间复杂度为 $O(1), O(n), O(n^2)$ 对数阶复杂度很少用到