算法的复杂度

远子 •  2021年03月01日

本文为《大话数据结构》中算法章节的读书笔记。

算法有五个特性:输入、输出、有穷性、确定性和可行性。

  • 输入:一个算法可以没有输出,比如生成随机字符串的算法。
  • 输出:算法至少有一个或多个输出。
  • 有穷性:算法在执行有限的步骤后会自动结束,不会出现死循环。
  • 确定性:相同的输入必定得到相同的输出。
  • 可行性:算法可以在计算机上运行,并得到正确结果。

设计算法的要求:

  • 正确性
  • 可读性
  • 健壮性
  • 时间效率高和存储量低

我们通常使用大 O 符号描述一个算法的时间复杂度。

大 O 符号(Big O Notation)又称为渐进符号,是用于描述函数渐进行为的数学符号。

大 O 表示法的计算方法:

  1. 用常数 1 取代运行时间中所有的加法常数;
  2. 在修改后的运行次数函数中,只保留最高阶项;
  3. 如果最高阶项存在且不是1,则去除与这个项相乘的常数。

得到的结果就是大 O 表示法。

时间复杂度

时间复杂度是指完成一个算法所需要的时间。

我们通常只讨论算法的最坏情况复杂度。

只保留最高阶项

假如有以下两个算法,其中 console.log("执行了一次") 的输出次数,视为执行该算法所需的步骤数:

function a(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log("执行了一次");
      console.log("执行了一次");
    }
  }
}

算法 B:

function a(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log("执行了一次");
      console.log("执行了一次");
    }
  }
  for (let i = 0; i< n; i++) {
    console.log("执行了一次");
  }
  console.log("执行了一次");
}

下表展示了规模 n 不断增加时,两个算法的执行步骤数:

次数算法A($2n^2$)算法B($2n^2 + 3n + 1$)
126
2815
55066
10200231
1002000020301
100020000002003001
10000200000000200030001
1000002000000000020000300001
100000020000000000002000003000001

当 n 逐渐增大时,算法 A 和算法 B 的步骤数趋于接近。

当 $n = 1000000$时,算法 B 是算法 A 的 $1.0000015$ 倍,省略 $3n + 1$ 的部分微乎其微,因此我们在计算时间复杂度时,通常只保留最高阶项。

我们认为算法 A 和算法 B 具有相同的时间复杂度,为平方阶,即:$O(n^2)$。

忽略系数

如果我们将 $2n^2$ 与更高阶项的算法比较时, $2n^2$ 的系数也是无关紧要的。

来看以下两个算法:

算法 A:

function a(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log("执行了一次");
      console.log("执行了一次");
    }
  }
}

算法 B:

function b(n) {
    for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        console.log("执行了一次");
      }
    }
  }
}

下表展示了规模 n 不断增加时,两个算法的执行步骤数:

次数算法A($2n^2$)算法B($n^3$)
121
288
550125
102001000
100200001000000
100020000001000000000
100002000000001000000000000
100000200000000001000000000000000
100000020000000000001000000000000000000
100000002000000000000001000000000000000000000

当 n 逐渐增大时,算法 B 的步骤数骤增。

当 $n = 10000000$ 时,算法 B 已经是算法 A 的 500 万倍,省略对 $ 2n^2$ 的常数 2 对算法 A 的影响是可以忽略不计的。

我们认为算法 A 为平方阶,即 $O(n^2)$。算法 B 为立方阶,即 $O(n^3)$。

常见的时间复杂度

算法函数阶术语
12$O(1)$常数阶
$2n + 3$$O(n)$线性阶
$3n^2 + 2n + 1$$O(n^2)$平方阶
$5log_2n + 20$$O(log_n)$对数阶
$2n + 3nlog_2n + 19$$O(nlogn)$线性对数阶
$6n^3 + 2n^2 + 3n + 4$$O(n^3)$立方阶
$2^n$$O(2^n)$指数阶
$n!$$O(n!)$阶乘阶

耗费时间从小到大依次是:

$O(1)$ < $O(log_n)$ < $O(n)$ < $O(nlogn) $< $O(n^2)$ < $O(n^3)$ < $O(2^n)$ < $O(n!)$ < $O(n^n)$

指数阶 $O(2^n)$ 和阶乘阶 $O(n!)$ 在 n 的值稍微大一点,都是噩梦般的运行时间,这种不切实际的算法时间复杂度一般不去讨论。

空间复杂度

空间复杂度是指完成一个算法所需要占用的存储空间。

我们在写代码时,完全可以用空间来换取时间,比如说,要判断某某年是不是闰年,你可能会花一点心思写了一个算法,而且由于是一个算法,也就意味着,每次给一个年份,都是要通过计算得到是否是闰年的结果。还有另一个办法就是,事先建立一个有2050个元素的数组(年数略比现实多一点),然后把所有的年份按下标的数字对应,如果是闰年,此数组项的值就是1,如果不是值为0。这样,所谓的判断某一年是否是闰年,就变成了查找这个数组的某一项的值是多少的问题。此时,我们的运算是最小化了,但是硬盘上或者内存中需要存储这2050个0和1。

(完)