时间复杂度
时间复杂度.png
- 时间复杂度O(1)
let i = 0;
i += 1;
- 时间复杂度O(n)
for(let i = 0; i<n; i++) {
console.log(i);
}
- 时间复杂度计算
O(1) + O(n) = O(n) // O(n) 足够大所以O(1)忽略不计
O(n) * O(n) = O(n^2) // 比如嵌套循环
O(logN) // 求2的多少次方等于 N
let i = i;
while(i < n) {
console.log(i);
i *= 2;
}
空间复杂度(代码运行时占据的内存大小)
// O(1) 只声明了单个变量
let i = 0;
i += 1;
// O(n) list添加了n个值占用n个内存单元
let list = []
for(let i=0; i< n; i++) {
list.push(i)
}
// O(n^2) 矩阵
const matrix = []
for(let i = 0; i<n; i++) {
martrix.push([]);
for(let j=0; j<n; j++) {
martrix[i].push(j)
}
}
