关于javascript:jsfor循环时间复杂度

在工作中，总是须要对数组进行循环解决，当数据越来越多的时候，就会导致解决的工夫比拟长。所以，这篇文章简略的重温一下工夫复杂度，以及简略测试一下，不同嵌套循环的解决工夫。

工夫复杂度：

定义：
在计算机科学中，工夫复杂性，又称工夫复杂度，算法的工夫复杂度是一个函数，它定性描述该算法的运行工夫。这是一个代表算法输出值的字符串的长度的函数。工夫复杂度罕用大O符号表述，不包含这个函数的低阶项和首项系数。应用这种形式时，工夫复杂度可被称为是渐近的，亦即考查输出值大小趋近无穷时的状况。

罕用的

在理论开发中，最常常遇到的还是 O(n²)，也就是双层for 循环。

上面进行测试一下不同循环形式所破费的工夫：

先创立 a， b 两个数组。

      for (let i = 0; i < 9999; i++) {        this.a.push({ id: i, name: 'a：' + i })      }      console.log("a数组",this.a)      for (let x = 0; x < 999; x++) {        this.b.push({ id: x, name: 'b：' +  x })      }      console.log("b数组",this.b)

c数组寄存， 他们 id 相等的对象
1，通过 for 循环嵌套 for 进行数据操作，

      const c = []       console.time('打印 for - for');       for(let i = 0; i< this.a.length; i++){        for(let x = 0; x< this.b.length; x++){          if (this.a[i].id === this.b[x].id){             c.push(this.a[i])          }        }       }      console.log("c数组",c)      console.timeEnd('打印 for - for');

此时所破费的工夫：打印 for - for: 120012.27807617188 ms

2，通过 forEach 循环嵌套 forEach 进行数据操作，

      const c = []       console.time('打印 forEach - forEach');       this.a.forEach( n => {          this.b.forEach(m => {          if (n.id === m.id) c.push(m)        })       })      console.log("c数组",c)      console.timeEnd('打印 forEach - forEach');

此时所破费的工夫：打印 forEach - forEach: 2006.343994140625 ms

3，通过 filter 和 includes 进行数据操作，

      console.time('打印 filter - includes');      const ids = this.a.map(m => m.id)      const c = this.b.filter(n => ids.includes(n.id))      console.log("c数组",c)      console.timeEnd('打印 filter - includes');

此时所破费的工夫：打印 filter - includes: 5.912841796875 ms

最初发现，通过 filter 和 includes 进行数据操作，工夫大大减少了，是因为 应用了 map

哈希表为无序 Map，插入、查找、删除的工夫复杂度均为O(1)Map 是 ES6 新出的一种数据结构，用来示意键值对，object也是键值对构造，Map算是对object的一种增强object的键只能为string，Map的键能够为任意值

参考：
双层循环遍历 缩小工夫复杂度
map的工夫复杂度_JavaScript ES6—Map的妙用