首页 > 算法 阅读:13,522

时间复杂度和空间复杂度

< 上一页算法是什么 递归算法下一页 >

算法是什么》一节提到,解决一个问题的算法可能有多种,这种情况下,我们就必须对这些算法进行取舍,从中挑选出一个“最好”的。

算法本身是不分“好坏”的,所谓“最好”的算法,指的是最适合当前场景的算法。挑选算法时,主要考虑以下两方面因素:
  • 执行效率:根据算法所编写的程序,执行时间越短,执行效率就越高;
  • 占用的内存空间:不同算法编写出的程序,运行时占用的内存空间也不相同。如果实际场景中仅能使用少量的内存空间,就应该优先选择占用空间最少的算法。

当问题对应的算法数量较少时(比如 2、3 种),我们可以编写出各个算法对应的程序,逐个在机器上运行,记录它们各自的执行时间和占用内存空间的大小,最终挑选出“最好”的算法。如果问题对应的算法数量有很多(比如 10 种,20 种),先前的挑选方式将不再适用,因为将各个算法一一编写成程序的工作量是巨大的,得不偿失。

实际开发中,我们往往采用“预先估值”的方法挑选算法。具体来讲,就是分析各个算法的实现过程(步骤),估算出它们各自的运行时间和占用的内存空间,进而挑选出“最好”的算法。用“预先估算”方式挑选算法时,我们习惯用时间复杂度表示一个算法的运行时间,用空间复杂度表示算法占用存储空间的大小。

接下来,我们就来了解一下如何估算一个算法的时间复杂度和空间复杂度。

时间复杂度

时间复杂度用于表示算法的执行时间。

接下来,我们以《算法是什么》一节中求 n! 的算法为例:

输入 n                 // 接收 n 的值
p <- 1                 // p 的初值置为 1
for i<-1 to n:    // i 的值从 1 一直到 n
    p <- p * i        // 将 p*i 的值赋值给 p
Print p                // 输出 p 的值

计算它的时间复杂度,只需经历以下几个步骤:

1) 统计算法中各个步骤的执行次数

整个算法中共有 5 行伪指令,它们各自的执行次数分别是:

输入 n                 <- 执行 1 次
p <- 1                 <- 执行 1 次
for i<-1 to n:    <- i 的值从 1 遍历到 n,当 i 的值为 n+1 的时候退出循环,总共执行 n+1 次
    p <- p * i         <- i 从 1 到 n 的过程,共执行 n 次
Print p                 <- 执行 1 次

统计算法中所有伪指令执行的总次数,结果为 2*n+4。显然,2*n+4 不是一个固定值,整个表达式值的大小取决于 n 的值。

2*n+4 可以直接作为算法执行时间的估值,也可以对它进行简化,用规范的形式表示算法的运行时间。

2) 简化算法的执行次数

通过统计各个算法中每条伪指令的执行次数,每个算法的运行时间都可以用类似 2*n+4、3*n2+4*n+5 这样的表达式表示。这就产生一个问题,如何比较各个表达式的大小呢?

首先,我们可以尝试对每个表达式进行简化,简化方法是:假设表达式中变量的值无限大时,去除掉那些对表达式结果影响较小的项。以 3*n2+4*n+5 为例,简化过程为:
  • 当 n 无限大时,3*n2+4*n 与 3*n2+4*n+5 的值非常接近,是否加 5 对表达式的值影响不大,因此表达式可以简化为 3*n2+4*n;
  • 当 n 无限大时,3*n2 的值要远远大于 4*n 的值,它们之间类似于 10000 和 1 之间的关系,因此是否加 4*n 对表达式最终的值影响不大,整个表达式可以简化为 3*n2
  • 当 n 无限大时,n2 的值已经超级大,是否乘 3 对最终结果影响不大,整个表达式可以简化为  n2

简化表达式的过程可以总结为:
  • 去掉表达式中所有的加法常数项,3*n2+4*n+5 中的 5 就是加法常数项;
  • 只保留表达式中变量指数最大的项,3*n2+4*n 中 n 的最大指数为 2,所以只保留 3*n2
  • 去掉常数系数,3*n2 中的 3 就是 n2 的常数系数。

基于“n 值无限大”的思想,3*n2+4*n+5 最终可以简化为 n2。无论多么复杂的表达式,都可以采用这种方式进行简化。

3) 大O记法表示时间复杂度

除了用 n 外,一些人还可能会用 a、b、c 等字符作为表达式中的变量。为此,人们逐渐达成了一种共识,即都用 n 作为表达式中的变量,并采用大 O 记法表示算法的执行时间。

采用大 O 记法表示算法的执行时间,直接套用如下的格式即可:

O(频度)

频度指的就是简化后的表达式。

采用大 O 记法,2*n+4 可以用 O(n) 表示,3*n2+4*n+5 可以用O(n2)表示。注意,如果一个算法对应的表达式中没有变量(比如 10,100 等),则用O(1)表示算法的执行时间。

如果一个算法的执行时间最终估算为O(n),那么该算法的时间复杂度就是O(n)。如下列举了常用的几种时间复杂度以及它们之间的大小关系:

O(1)< O(logn) < O(n) < O(n2) < O(n3) < O(2n)

O(1)是最小的,对应的算法的执行时间最短,执行效率最高。

空间复杂度

空间复杂度衡量的是算法执行过程占用的内存空间的大小。

比较多个算法占用的内存大小,本质上比较的是各个算法执行过程中额外申请的内存空间的大小。举个简单的例子:

输入 n
A[i...n] = {1...n}    <- 额外申请 n 个空间

根据 n 的值,算法执行时需要申请 n 个整数的内存空间,n 的值越大,额外申请的内存空间就越多。

与时间复杂度的表示方法一样,空间复杂度也采用大 O 记法表示。算法空间复杂度的估算方法是:
  • 如果算法中额外申请的内存空间不受用户输入值的影响(是一个固定值),那么该算法的空间复杂度用 O(1) 表示;
  • 如果随着输入值 n 的增大,算法申请的存储空间成线性增长,则程序的空间复杂度用 O(n) 表示;
  • 如果随着输入值 n 的增大,程序申请的存储空间成 n2 关系增长,则程序的空间复杂度用 O(n2) 表示;
  • 如果随着输入值 n 的增大,程序申请的存储空间成 n3 关系增长,则程序的空间复杂度用 O(n3) 表示;

多数场景中,挑选 "好" 算法往往更注重的是时间复杂度,空间复杂度只要处于一个合理的范围即可。

关注微信公众号「站长严长生」,在手机上阅读所有教程,随时随地都能学习。本公众号由C语言中文网站长运营,每日更新,坚持原创,敢说真话,凡事有态度。

魏雪原二维码
微信扫描二维码关注公众号

< 上一页算法是什么 递归算法下一页 >