通过js示例讲解时间复杂度与空间复杂度

1. 博客背景

今天有同事在检查代码的时候，由于函数写的性能不是很好，被打回去重构了，细思极恐，今天和大家分享一篇用js讲解的时间复杂度和空间复杂度的博客

2. 复杂度的表示方式

之前有看过的，你可能会看到这么一串东西

T(n) = O(f(n)) S(n) = O(f(n)) 

这个叫做大O表示法，其中的T代表的是算法需要执行的总时间

S表示的算法需要的总空间

f(n)表示的是代码执行的总次数

举个例子

function go(n) {  var item = 0;   // 这里执行了一次 for (var i = 0; i < n; i++) {  //这里执行了N次  for (var j = 0; j < n; j++) {   //这里执行了n*n次   item = item + i + j;   //这里执行了n*n次  } } return item; //这里执行了一次}

所以说上边这段代码是 1+n+n*n*2+1=2+n+2n²

也就是说 T(n) = O(f(2+n+2n²))

然后之前说了时间复杂度看的是一个代码执行的时间的趋势， 所以说在N，也就是规模比较大的时候，那些常量是起不到决定性的作用的，所以这个时候我们忽略这些常量，这里的例子是一个单段的代码，这里只看最大量级的循环就可以了

所以最后的这个代码的时间复杂度是T(n) = O(n²)

大家可以想想一下数据中平方的曲线图

3. 时间复杂度

3.1 时间复杂度的定义

首先什么是时间复杂度，时间复杂度这个定义如果在之前没有接触过的话，你可能会认为他代表的是一个代码执行的时间，其实不然，算法的时间复杂度就是说一个算法的执行时间根据数据规模增长的一个趋势，并不是说代码执行的具体时间

3.2 几种常见的时间复杂度

最简单的O(n)

for (var i = 0; i < n; i++) { sum += i; }

通俗易懂，这段代码的执行时间完全由N来控制，所以说T(n) = O(n)

当然还有个更简单的O(1)

function total(n) {console.log(1)}

无论怎么样，这段函数不受任何参数影响，代码走一遍就完事，这种的代码用T(n) = O(1) 表示

T(n) = O(n²)

上边的例子已经说了一个了两层循环的那种，在举一个时间复杂度多块代码的情况时间复杂度的计算方式

function go(i) { var sum = 0; for (var j = 0; j < i; j++) {  sum += i; } return sum;}function main(n) { var res = 0; for (var i = 0; i < n; i++) {  res = res + go(i); // 这里是重点 }}

在上边的代码种第二段代码里边调用了第一段代码，所以说在这个代码里边是

go：（1+n）

在main函数里边的时候是(1+n*go)=(1+n+n*n)

所以最后的时间复杂度是T(n) = O(n²)