在工作中,总是须要对数组进行循环解决,当数据越来越多的时候,就会导致解决的工夫比拟长。所以,这篇文章简略的重温一下工夫复杂度,以及简略测试一下,不同嵌套循环的解决工夫。
工夫复杂度:
定义: 在计算机科学中,工夫复杂性,又称工夫复杂度,算法的工夫复杂度是一个函数,它定性描述该算法的运行工夫。这是一个代表算法输出值的字符串的长度的函数。工夫复杂度罕用大 O 符号表述,不包含这个函数的低阶项和首项系数。应用这种形式时,工夫复杂度可被称为是渐近的,亦即考查输出值大小趋近无穷时的状况。
罕用的
符号 | 含意 |
---|---|
O(1) | 常数 |
O(log(n)) | 对数 |
O(n) | 线性 |
O(n²) | 平方 |
O(2^n) | 指数 |
在理论开发中,最常常遇到的还是 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 的妙用