时间复杂度

时间复杂度.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)
  }
}