算法：时间复杂度和空间复杂度(一)

1、数据结构：计算机存储、组织数据的方式

栈、队列、链表、集合、字典、树、图、堆

2、算法：一系列解决问题的清晰指令

3、时间复杂度: 描述该算法的运行时间

image.png

• 1. O(1) 只执行一次

let i = 0;
i += 1

• 2. O(n) 执行n次

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

• 3. O(1) + O(n) = O(n) 时间复杂度先后排列，要相加，取增长趋势更快的时间复杂度

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

• 4. 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)
      }
 }

• 5. O(logN)

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

4、空间复杂度：在运行过程中临时占用的存储空间大小

• 1. O(1)

let i = 0;
i += 1

• 2. O(n)

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

• 3. 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)
     }
}

算法：数组(二) - 简书 (jianshu.com)