时间空间复杂度计算

1. 时间复杂度计算

• 定性描述该算法的运行时间

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)

let i = 0
i += 1
for(let i = 0; i < n; i++) {
  console.log(i)
}

O(n) * O(n) = O(n^2)

for(let i = 0; i < n; i++) {
  for(let j = 0; j < n; j++) {
    console.log(i, j)
  }
}

O(logN)

let i = 1
while(i < n) {
  console.log(i)
  i *= 2
}

2. 空间复杂度

• 算法在运行过程中临时占用存储空间大小的度量

O(1)

let i = 0
i += 1

O(n)

const list = []
for(let i = 0; i < n; i++) {
  list.push(i)
}

O(n^2)

const matrix = []
for(let i = 0; i < n; i++) {
  matrix.push([])
  for(let j = 0; j < n; j++) {
    matrix[i].push(j)
  }
}