大家好，我是小丞同学，一名大二的前端爱好者
这篇文章是数据结构与算法专栏的第一篇博文
非常感谢你的阅读，不对的地方欢迎指正
愿你忠于自己，热爱生活
知识点抢先看
算法基础
计算时间复杂度
计算空间复杂度
数据结构和算法的学习指南
文末有惊喜噢~
专栏简介
按照惯例，每个专栏的第一篇文章都会简单的介绍一下这个专栏的内容，以及未来的更文计划
本专栏 【化解数据结构】，将在这里总结自己学习数据结构和算法的学习笔记，从这篇算法入门开始，未来更文将涉及栈、队列、链表、堆、树、图…等数据结构，以及经典排序算法，算法设计思想等进阶算法…，同时将会结合 LeetCode 题目对每篇文章进行巩固和提升，欢迎大家关注本专栏或添加作者本文联系方式，一起努力，一起刷题，一起进步
（图片来源于慕课网截图）
引言
在正式写这个之前，先来讲讲为什么要学数据结构和算法？
为了计算出最优解
这是我的答案，当我打开 LeetCode 第一题两数之和的提交记录时，我发现自己半年前的代码，耗时 240ms，内存占用 40多mb 时，我感受到了它的魅力
在最新的代码中，我采用了 map 的容器，通过 has 方法替代了先前采用的 indexof 方法，从查到的资料来看，map 的查找的时间复杂度为 O(1) ，indexOf 为 O(n) ，在 map 的底层实现中采用了哈希表的数据结构，极大的优化了查找的复杂度
接下来我们来看看如何计算时间、空间复杂度！
一. 大 O 表示法
关于复杂度的计算，我们采用的是 大 O 表示法 ，它用来描述算法性能和复杂程度
常见的表示
符号大O标记法 名称
O(1) 常数
O(log N) 对数
O(N) 线性
O(N log N) 对数多项式
O(N^2) 二次
O(2^N) 指数
O(N!) 阶乘
大 O 表示法一般考虑的是 CPU 占用时间，它可以粗略的了解代码运行的时间效率
例如
function test(num){ return ++num; }
我们调用这个函数一次，执行时间是 t ，我们再调用一次，执行时间还是 t，和传入的参数无关， test 函数的性能都一样，因此它的复杂度为 O(1)
当循环 n 次时，就是 O(n)
二. 时间复杂度
大 O 表示法表明的是该段代码执行时间随数据规模增大的变化趋势，它的特点是
只关注量级最大的时间复杂度
常见的时间复杂度量级 O(1) < O(logn) < O(n) < O(n^2)
对于 O(2)、O(3) 这些，我们都叫做 O(1) 常数级
例如：
1. O(1)
let i = 0; i += 1; // 每次执行代码只执行一次 O(1)
这段代码每次只执行一次，因此为 O(1)
2. O(n)
for (let j = 0; j < n; j++) { console.log(j); }
再上面这段代码中，我们每次都需要执行 n 次的 log ，因此我们可以把它看作 O(n)
同样的我们再来看一个
let i = 0; i += 1; for (let j = 0; j < navigator; j++) { console.log(j); }
这种代码我们经常写，前面是我们刚刚计算的 O(1)，后面是 O(n) ，它们并行排列，时间复杂度相加，取最大的那个
因此它的时间复杂度同样是 O(n)
3. O(log(n))
while (i < n) { console.log(i); i *= 2; }
对于 log(n) 的情况，在个时间复杂度是很好的，当然 O(1) 是最好的，但是在解题的时候，如果能优化到 log(n) 也是很不错的了
那它是如何计算的呢？
我们可以看到，这里采用了 变量i来控制循环的终止，每次循环体中，都需要 2 * i 的操作
因此对于时间复杂度的计算 2^t = n 解得 t = log(n)
4. O(n^2)
for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { console.log(i); } }
对于这种嵌套排列，时间复杂度是 n^2 ，外面一层 n ，里面一层 n 乘一下就是 n^2，冒泡排序的时间复杂度就是 O(n^2)
关于时间复杂度就介绍这么多，其他的思路都差不多
三、空间复杂度
空间复杂度表示的是：存储空间随数据规模的增长趋势，在 LeetCode 中最直接的反应就是内存消耗
例如
1. O(1)
let i = 0;
在这里我们申请了单个变量的内存空间，为 O(1)
2. O(n)
let arr = [] for(let i = 0;i < n;i++) { arr.push(i) }
像这样的一个数组，并给它填满值，n 越大，它需要分配的空间就越多，它的空间复杂度就是 O(n)
3. O(n^2)
int arr = [][]// 遍历赋值
声明一个二维数组，填满值，它的空间复杂度就是 O(n^2) ，你可以理解为一个矩阵，n*n 为 n^2
总结
复杂度计算按最高阶来计算
时间、空间复杂度描述的都是随数据规模的变化趋势
时间复杂度的重点在于循环嵌套
空间复杂度关注于内存
