删除|字节算法大神熬了三个通宵整理的数据结构与算法笔记（万字长文）( 二 )

用什么来衡量呢？就是用复杂度来，包括时间复杂度和空间复杂度，通常用大O复杂度表示法。
时间复杂度：并非具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的「变化趋势」，因此也叫渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
PS: 可以类比数学中的极限问题。
复杂度量级表示：

复杂度量级比较：

空间复杂度：
全称渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。
常见的空间复杂度有：O(1) O(n) O(n^2).
复杂度分析法则
1. 只关注循环执行次数最多的一段代码；
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度；
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。
最好、最坏、平均、均摊时间复杂度
1. 最好情况时间复杂度（best case time complexity）：最理想的情况下，执行一段代码的时间复杂度。
2. 最坏情况时间复杂度（worst case time complexity）：最糟糕的情况下，执行一段代码的时间复杂度。
3. 平均情况时间复杂度（average case time complexity）：加权平均时间复杂度。
场景分析：从一个无序数组中查找指定的元素x并返回。
case1: 若x在第一个位置出现，则查找时间复杂度为O(1) ，该情况为最好时间复杂度；
case2: 若x在该数组中不存在，则需要遍历整个数组，复杂度为O(n) ，为最坏状况复杂度；
而平均复杂度就是根据x在数组中每个位置出现的概率求出的加权平均值。
4. 均摊时间复杂度（amortized time complexity）
该复杂度比较特殊，通常用于对一个数据结构一组连续的操作：大部分情况下复杂度很低，个别情况下复杂度较高，而且前后一般规律性的出现。此时，可以将这些操作放在一起分析，将复杂度较高的操作平摊到其他复杂度低的操作中。这种方法通常称为「摊还分析」。
线性表&非线性表
线性表（Linear List）：
由n (n>=0)个数据元素组成的有限序列。每个元素均有一个直接前驱和直接后继元素。
PS: 可以认为，每个元素的前后元素都是唯一的（如果存在）。
常用的线性表有：数组、链表、栈和队列等。示意图：

非线性表，树、图等，示意图：

数组&链表
数组：

单链表：

单链表插入和删除操作：

循环链表：

双向链表：

数组&链表比较
内存分布对比：

查询时间复杂度对比：

数组&链表小结：
1. 数组内存空间连续，链表内存空间非连续；
2. 随机访问（下标访问）：数组支持随机访问，随机访问的时间复杂度为O(1)；链表不支持随机访问，时间复杂度为O(n)；
3. 插入数据：由于数组内存空间连续，在数组指定位置插入元素时需要做数据搬移，时间复杂度为O(n)；链表则直接插入即可，时间复杂度为O(1) 。
栈&队列
示意图：

栈：后进先出（Last In First Out LIFO）

栈可以用数组或链表实现：数组实现的栈称为「顺序栈」，链表实现的栈称为「链式栈」。
使用场景：函数调用栈、表达式求值、括号匹配、浏览器前进后退等。
队列：先进先出（First In First Out FIFO）
操作：
1. 入队（enqueue）：将一个数据元素插入队列尾部；
2. 出队（dequeue）：从队列头部取一个数据元素。
示意图：

队列可以用数组或链表来实现：数组实现的队列称为「顺序队列」