数据结构与算法笔记（一）

时间&空间复杂度

数据结构和算法的本质是解决“快”和“省”的问题：即如何让代码运行得更快、更省存储空间。

用什么来衡量呢？就是用复杂度来，包括时间复杂度和空间复杂度，通常用大 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）：从队列头部取一个数据元素。

示意图：

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

，链表实现的队列称为「链式队列」。

阻塞队列：

“生产者-消费者”模型。即队列的两端分别对应生产者和消费者，队列满的时候，生产者阻塞等待；队列空的时候，消费者阻塞等待。示意图：

实现类有 ArrayBlockingQueue、LinkedBlockingQueue 等。

小结

本文主要总结了复杂度和线性表的一些概念。

复杂度

衡量代码执行速度和占用空间的标尺。包括时间复杂度和空间复杂度，用大 O 复杂度表示法。

线性表

常用的线性表包括数组、链表、栈、队列等。其中，可以认为数组和链表是最基本的数据结构，其他一些更复杂的数据结构通常可以基于二者实现或经过变形而来。

Stay hungry, stay foolish.