架构师训练营 1 期第 8 周：性能优化（二）- 总结

本文主要介绍常见的数据结构及其使用场景、进化规律，最后介绍几种经典算法的思路。

一、时间复杂度和空间复杂度

二、常见数据结构

数组

• 创建数组必须要内存中一块连续的空间。

• 数组中必须存放相同的数据类型。

• 随机快速读写是数组的一个重要特性，根据数 组的下标访问数据，时间复杂度为 O(1)。

链表

• 链表可以使用零散的内存空间存储数据。

• 所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。

• 要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是 O(N)。

• 链表中增删数据要比数组性能好的多。

Hash 表

• 数组链表结合，实现快速查找和快速增删。同时可以解决 Hash 冲突问题。

• 利用 hash 碰撞进行 hash 攻击，会导致 hash 表退化成一个链表

栈

• 数组和链表都被称为线性表。

• 栈就是在线性表的基础上加了这样的操作限 制条件：后面添加的数据，在删除的时候必 须先删除，即通常所说的“后进先出”。

• 线程运行时专有内存被称为线程调用栈，实现了任何时候，程序执行的局部变量总是在栈顶元素，每个函数执行有自己的栈帧，当前执行的函数的栈帧总是在栈的最顶端

队列

• 队列也是一种操作受限的线性表，栈是后进先出，而队列是先进先出。

• 典型应用场景：生产者消费者；阻塞等待的线程被放入队列。

• 用队列搜索好友中关系最近的有钱人。

• 逐一进队出队，出队列时进行检查是否是有钱人，如果不是，继续将后续节点放入队列，直到找到有前人

• 用队列搜索最短路径。

• 思路同上，需要记录沿途节点和路径，出队时判断后续节点是否到达终点，如果不是终点，继续将后续节点放入队列，如果是终点，则找到最短路径

二叉树

• 左子树上所有结点的值均小于或等于它的根结点的值。

• 右子树上所有结点的值均大于或等于它的根结点的值。

• 左、右子树也分别为二叉排序树。

平衡二叉（排序）树

• 从任何一个节点出发，左右子树深度之差的绝对值不超过 1。

• 左右子树仍然为平衡二叉树。

• 旋转二叉树恢复平衡

• 插入时，最多只需要两次旋 转就会重新恢复平衡。

• 删除时，需要维护从被删节 点到根节点这条路径上所有 节点的平衡性，时间复杂度 O(logN)。

红黑（排序）树

• 每个节点只有两种颜色：红色和黑色。

• 根节点是黑色的。

• 每个叶子节点（NIL）都是黑色的空节点。

• 从根节点到叶子节点，不会出现两个连续的红色节点。

• 从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。

• 增删节点的时候，红黑树通过染色和旋转，保持红黑树满足定义。

• 红黑树 VS 平衡二叉树

• 红黑树最多只需 3 次旋转就会重新达成红黑平衡，时间复杂度 O(1)。

• 在大量增删的情况下，红黑树的效率更高。

• 红黑树的平衡性不如平衡二叉树，查找效率要差一些。

跳表

• 将数据构建成原始链表，然后将部分中间数据跳起来构建新的链表，查找时先检索新列表，再检索原始链表，以实现快速查找

• 实现简单，很多程序中使用跳表代替红黑树，来实现排序数据的快速查找

• 数据冗余多，空间复杂度大

• 以资源换性能，以简单换复杂

三、经典算法

穷举算法

• 把所有的可能条件都列出来，然后在列出的所有可能性中去找最优的解。

• 方法比较暴力，当穷举数目不多的时候非常有效。

递归算法

• 快速排序算法，时间复杂度： n * log(n)

贪心算法

• 贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

• 解决背包问题：小偷背了一个 4 磅背包去商城偷东西，将哪些商品放入背包才能收益最大化。

• 先将价值最大的音响放入 4 磅的背包，如果还有空间，继续放剩下价值最大的商品，如果没有空间就不在放了，这里音响 4 磅，正好放满书包，这样的算法选择显然不是最优解，最优解应该选择笔记本+吉他，总重量也是 4 磅，价值总和为 3500 美元大于音响的 3000 美元。

改进贪心算法 - 迪杰斯特拉算法（最快路径）

• 找出“最便宜”的节点，即可在最短时间内到达的节点。

• 更新该节点的邻居的开销，检查是否有前往它们的更短路径，如果有，就更新其开销 。

• 重复这个过程，直到对图中的每个节点都这样做了。

• 计算最终路径。

• 迪杰斯特拉算法的核心是找到起点到每个节点的最快路径

动态规划

• 通过找到合适的角度，将所求解的目标值在某（几）个维度上展开，将一个大问题拆解 为若干小问题，从小问题的最优解，寻找大问题的最优解

• 动态规划算法解决背包问题

• 每个动态规划算法都从一个网格开始，背包问题的网格如下：

• 最后 4 磅的最优解等于 1 磅最优解+3 磅的最优解，1500+2000+3500 美元

遗传算法

• 遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

• 遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、 初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

• 遗传算法解决背包问题：80 公斤背包装哪些物品价值最大？

• 基因编码与染色体

• 适应函数与控制参数

• 选择算法

• 交叉遗传

• 遗传算法得到的不是最优解