文章为极客时间《数据结构与算法之美》的学习笔记。
要点：辩证思考，多想为什么，多练。

什么是数据结构？

数据结构就是指一组数据的存储结构。

什么是算法？

算法就是操作数据的一组方法
数据结构和算法相辅相成。数据结构是为算法服务的，算法要作用在特定的数据结构之上。数据结构是静态的，它只是组织数据的一种方式，如果不在它的基础上操作、构建算法，孤立存在的数据结构没有用。

常见的十种数据结构：

数组、链表、栈、队列、散列表、
二叉树、堆、跳表、图、Trie树

常见的十种算法：

递归、排序、二分查找、搜索、哈希算法、
贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法

时间复杂度分析

大O时间复杂度表示法，大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，也叫渐进时间复杂度，简称时间复杂度。

• 关注循环执行次数最多的代码
• 加法法则：总复杂度等于量级最大的那段代码的复杂度
• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
• 忽略常量级的执行次数，只关注与规模相关的执行代码（不管常量多大，都可以忽略）
• 可以忽略常量系数：O(Cf(n)) = O(f(n))
• 当数据规模是两个的时候，代码复杂度由两个数据的规模来决定，比如O(m+n) 、O(m*n)

常见时间复杂度量级

多项式量级：

• 常量阶 O(1)：一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行代码，其时间复杂度也是O(1)
• 对数阶 O(log n)：不管是以2为底，还是以3为底，还是以10为底，可以把所有对数阶的时间复杂度都记成O(log n)，因为对数直接可以进行互相转换：log₃n = log₃2 * log₂n，在采用大O标记复杂度的时候，可以忽略系数，即O(log₂n)=O(log₃n)，所以在对数阶时间复杂度的表示方法里，忽略对数的底，统一表示为O(log n)。
• 线性阶 O(n)
• 线性对数阶 O(n log n)
• 平分阶 O(n²)、立方阶 O(n³)...k次方阶 O(n^k)

非多项式量级(比较低效)：

• 指数阶 O(2ⁿ)
• 阶乘阶 O(n!)

空间复杂度分析

空间复杂度全称是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。

常见空间复杂度

O(1)、O(n)、O(n²)

为什么要做复杂度分析？

通过统计、监控得到的算法执行的时间和占用的内存大小，这种方法非常依赖测试环境、测试结果受数据规模的影响很大，所以需要一个不用具体的数据来测试，就可以粗略估计算法的执行效率，即时间复杂度、空间复杂度分析。时间复杂度和空间复杂度分析不受外界因素的影响，可以与实际性能测试相辅相成。在编程过程中，需要带着复杂度分析的思维去写代码。

最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度

部分代码会随着输入数据的顺序、位置的不同，时间复杂度存在量级的差距，为了表示代码在不同情况下的不同时间复杂度，引入三个概念：最好时间复杂度、最坏时间复杂度和平均情况时间复杂度。

• 最好时间复杂度：在最理想的情况下，执行这段代码的时间复杂度
• 最坏时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度
• 平均情况时间复杂度：平均情况下的复杂度，全称：加权平均时间复杂度或者期望时间复杂度，会将每种情况出现的概率计算在其中。

均摊时间复杂度

对应的分析方法：摊还分析（平摊分析）
对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

均摊时间复杂度是一种特殊的平均时间复杂度

---

最后的备注：
markdown 如何输入上下标（如平方指数等）
输入上标，如：x2，则输入 x²
输入下标，如：x0，则输入 x₀