什么是空间复杂度?
算法在运行过程中临时占用存储空间大小的度量,和时间复杂度表示一样,一个函数,用大 O 表示,例如 O (1)、O (n)、O (^2 )...
基础案例
O(1)
这段代码因为只声明了单个变量,单个变量所占用的内存永远是 1。
let i = 0
i += 1
O(n)
这段代码主要声明了变量 list 和变量 i,但是变量 list 的元素个数会受 n 的影响,所以时间复杂度是 O (n) 而变量 i 的时间复杂度 O (1) 两个相加时可忽略不计。
const list = []
for (let i = 0; i < n; i++) {
list.push(i)
}
O(n ^ 2)
我们平时用的栅格布局(一行里面包括多少列)其实也可以用矩阵来表示。这段代码主要声明了 matrix 变量,是一个数组,因为是嵌套循环,所以数组的元素个数为 n * n 为 n ^ 2。
const matrix = []
for (let i = 0; i < n; i++) {
matrix.push([])
for (let j = 0; j < n; j++) {
matrix[i].push(j)
}
}
标签:matrix,++,复杂度,list,let,空间,什么,变量
From: https://blog.51cto.com/u_12639291/6196407