前言
本文主要记录了数据结构、算法、数据结构与算法的关系以及算法的时间复杂度、空间复杂度。
数据结构
数据结构是计算机存储、组织数据的方式。
算法
算法是一系列解决问题的清晰指令。
数据结构与算法的关系
程序 = 数据结构 + 算法
数据结构为算法提供服务，算法围绕数据进行操作。
时间复杂度
用来描述算法的运行时间。用 O 表示，常见的有O(1), O(n), O(n^2), O(log^n)...
图中直观表示了O(1), O(n), O(n^2), O(log2^n)的大小关系。
O(1)
let i = 1;
i++;
上述代码执行一遍就结束了，所以其时间复杂度为O(1)。
O(n)
for(let i = 0;i < n;i++){
console.log(i);
}
上述代码中有一个循环，需要执行n遍，所以其时间复杂度为O(n)。
O(1) + O(n) = O(n)
因为当n足够大时，1就忽略不计了。所以O(1) + O(n) = O(n)。
let i = 1;
i++;
for(let j = 0;j < n;j++){
console.log(j);
}
O(n^2)
for(let i = 0;i < n;i++){
for(let j = 0;j < n;j++){
console.log(i,j);
}
}
上述代码中有两个循环进行嵌套，需要执行n*n遍，所以其时间复杂度为O(n)*O(n)=O(n^2)。
O(log2^n)
let i = 1;
while(i < n){
i * = 2;
上述代码中有一个循环，需要执行到 2的x次方大于等于 n，才停止执行，所以其时间复杂度为O(log2^n)。
空间复杂度
用来描述算法的运行时所占用的内存空间。用 O 表示，常见的有O(1), O(n), O(n^2)...
O(1)
let i = 1;
i++;
上述代码只声明了一个变量，所以其空间复杂度为O(1)。
O(n)
const list = [];
for(let i = 0;i < n;i++){
list.push(i);
}
上述代码中有一个循环，需要执行n遍，循环每执行一次就向数组中添加一个数组成员，占用一块地址空间，所以其空间复杂度为O(n)。
O(n^2)
const list = [];
for(let i = 0;i < n;i++){
list.push(i);
for(let j = 0;j < n;j++){
list[i].push(j);
}
}
上述代码中有两个循环进行嵌套，需要执行n*n遍，循环每执行一次就向矩阵中添加一个成员，占用一块地址空间，所以其空间复杂度为O(n^2)。
常用算法的时间\空间复杂度
本文到此结束
如果大家还有什么其他想法，欢迎在评论区交流！
标签：++,复杂度,list,算法,let,空间,数据结构 From： https://blog.51cto.com/u_15718546/5748196