算法的复杂度

算法（algorithm）的定义

算法是解题方案的准确而完善的描述，是一系列解决问题的清晰指令。其实就是解决一个问题的完整性描述。

算法的效率

既然算法是解决问题的描述，而解决同一问题的方法也是多种多样的，只是在这过程中我们所使用的时间或时间以外的代价（计算机消耗的则为内存）不一样。为了更快、更好、更强的提高算法的效率，很多时候一个优秀的算法就在于它与其他实现同一问题的算法相比，在时间和空间（内存）上得到明显的降低。

算法的效率主要由以下两个复杂度来评估：

设计算法时，时间复杂度要比空间复杂度更容易出问题，所以一般情况一下我们只对时间复杂度进行研究。

时间复杂度

算法的时间复杂度是指算法需要消耗的时间资源。

一个算法执行所消耗的时间理论上是不能算出来的，虽然我们可以在程序中测试获得。但是我们不可能也没必要对每个算法进行测试，只需知道大概哪个算法执行所花费的时间多，哪个花费的时间少就行了。如果一个算法所花费的时间与算法中代码语句执行次数成正比，那么哪个算法执行语句越多，它的花费时间也就越多。我们把一个算法中的语句执行次数称为时间频度。通常用 T(n) 表示。

在时间频度 T(n) 中，n 又代表着问题的规模，当 n 不断变化时，T(n) 也会不断地随之变化。为了了解这个变化的规律，时间复杂度这一概念就被引入了。一般情况下算法的重复执行次数为问题规模 n 的某个函数，也就是时间频度 T(n)。如果有某个辅助函数 f(n)，当趋于无穷大的时候，T(n)/f(n) 的极限值是不为零的某个常数，那么 f(n) 是 T(n) 的同数量级函数，记作 T(n)=O(f(n))。算法执行时间的增长率与 f(n) 的增长率正相关，被称为算法的渐进时间复杂度，简称时间复杂度。

一般来说，计算机算法是问题规模 n 的函数 f(n)，算法的时间复杂度也因此记做 T(n)=O(f(n))。

大O表示法

用 O(n) 来体现算法时间复杂度的记法被称作大O表示法。

一般我们我们评估一个算法都是直接评估它的最坏的复杂度。

大O表示法 O(f(n)) 中的 f(n) 的值可以为 1、n、logn、n^2 等，所以我们将 O(1)、O(n)、O(logn)、O( n^2 ) 分别称为常数阶、线性阶、对数阶和平方阶。下面我们来看看推导大O阶的方法，有以下三种规则：

1. 用常数 1 取代运行时间中的所有加法常数
2. 只保留最高阶项
3. 去除最高阶的常数

• 常数阶

1
2
3
4

let sum = 0, n = 10; // 语句执行一次
let sum = (1 + n) * n/2; // 语句执行一次
console.log(`The sum is : ${sum}`); // 语句执行一次
// 这样的一段代码它的执行次数为 3。我们套用规则 1，则这个算法的时间复杂度为 O(1)，也就是常数阶。

• 线性阶

1
2
3
4
5
6

let i = 0; // 语句执行一次
while (i < n) { // 语句执行 n 次
  console.log(`Current i is ${i}`); // 语句执行 n 次
  i++; // 语句执行 n 次
}
// 这个算法中代码总共执行了 3n + 1 次，根据规则2和3，因此该算法的时间复杂度是 O(n)。

• 对数阶

1
2
3
4
5

let number = 1; // 语句执行一次
while (number < n) { // 语句执行 logn 次
  number *= 2; // 语句执行 logn 次
}
// 上面的算法中，number 每次都放大两倍，我们假设这个循环体执行了 m 次，那么 2^m = n，即 m = logn，所以整段代码执行次数为 1 + 2 * logn，则 f(n) = logn，时间复杂度为 O(logn)。

• 平方阶

1
2
3
4
5
6

for (let i = 0; i < n; i++) { // 语句执行 n 次
  for (let j = 0; j < n; j++) { // 语句执行 n^2 次
     console.log('I am here!'); // 语句执行 n^2
  }
}
// 上面的嵌套循环中，代码共执行 2 * n^2 + n，则 f(n) = n^2。所以该算法的时间复杂度为 O(n^2)

常见时间复杂度的比较

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

空间复杂度

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

引用

算法的时间复杂度和空间复杂度