架构师训练营第八周学习总结

时间复杂度

并不是计算程序具体运行的时间，而是算法执行语句的次数。O(1)，O(logn), O(n^a)属于多项式时间复杂度。O(a^n)和 O(n!)属于非多项式时间复杂度。

空间复杂度

一个算法在运行过程中临时占用存储空间大小的度量。O(n)表示需要临时占用 n 个数据。

NP 问题

P 问题：能在多项式时间复杂度内解决的问题

NP 问题：能在多项式时间复杂度内验证答案正确与否的问题。（典型：我可以在多项式时间复杂度内判断一个数字排列是否符合数独，但是却没办法在多项式时间复杂度内求解数独）

NP-hard 问题：比 NP 问题更难的问题（NP 问题的解法可以规约到 NP-hard 问题的解法）

NP 完全问题：是一个 NP-hard 问题，也是一个 NP 问题

数组

连续空间；数组中存放相同数据类型；随机快速读写。增删数据涉及数据搬迁，复杂度高。

链表

链表可以使用零散的内存空间存储数据。所以链表中每个数据元素都必须包含一个指向下一个数据元素的内存地址。

数组和链表可以结合起来，实现快速查找和快速增删

Hash 表

既要求快速访问数据，又希望快速增删数据

栈

数组和链表都被称为线性表。栈就是在线性表的基础上加了这样的操作限制条件：后进先出。

队列

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

树

一个结点可能有多个后继，最多一个前驱。二叉排序树是一种典型的树。左子树的所有结点均小于或等于根节点的值，右子树所有结点的值均大于或等于根节点的值。二叉树的时间复杂度一定是 O(longn)吗？其实未必，如果是不平衡的，可能退化成 O(n)。但是平衡二叉排序树的复杂度均为 O(n)。对于平衡二叉树，从任何一个节点出发，左右子树深度之差的绝对值不超过 1，并且左右子树仍然为平衡二叉树。不平衡的二叉树通过旋转来恢复平衡。插入时，最多只需要两次旋转就可以恢复平衡。删除时，需要维护从被删节点到根节点这条路径上所有节点的平衡性，时间复杂度是 O(logn)。

红黑树

1）每个结点要么是黑色，要么是红色。

2）根节点是黑色。

3）叶子节点（NIL）是黑色。

4）从根节点到叶子节点，不会出现连续的红色节点。

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

红黑树是在排序二叉树的前提下附加了以上的约束条件，使得排序二叉树达到近似平衡的目的。

红黑树 VS 平衡二叉树

红黑树最多只需要 3 次旋转就会重新达成红黑平衡，时间复杂度是 O(1)。在大量增删的情况下，红黑树的效率更高。但是，红黑树的平衡性不如平衡二叉树，查找效率差一点点。

Dijkstra 算法

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

2. 更新该阶段的邻居的开销，检查是否有前往它们的更短路径，如果有，就更新开销。

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

4. 计算最终路径。

动态规划

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

遗传算法

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化工程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；产生编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。遗传算法得到的不一定是最优解：

Web 请求一次网络通信的历程

OSI 七层模型和 TCP/IP 四层模型

网络数据包格式

物理层

物理层负责数据的物理传输，计算机输入输出的只能是 0，1 这样的二进制数据，但是在真正通信的线路里面有光纤，电缆，无线等各种设备。光信号和电信号，以及无线电磁信号在物理上是完全不同的，如何让这些不同的设备能够理解，处理相同的二进制数据，这就是物理层要解决的问题。

链路层

链路层就是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流量控制等。链路层会定义帧的大小，称为最大传输单元（MTU）。数据链路层会将封装好的帧添加一个帧头，帧头记录的一个重要信息就是发送者和接受者的 MAC 地址。

网络层

网络层 IP 协议使得互联网应用根据 IP 地址就能访问到目标服务器，请求离开 APP 后，到达运营商的交换机，交换机会根据这个 IP 地址进行路由转发，可能中间会经过很多个转发节点，最后数据到达目标服务器。网络层的数据需要交给链路层进行处理，而链路层帧的大小定义了最大传输单元，网络层的 IP 数据必须要小于最大传输单元才能进行网络传输。

传输层协议

IP 协议部署一个可靠的通信协议，不会建立稳定的通信链路，并不会确保数据一定送达。要保证通信的稳定可靠，需要传输层协议 TCP。TCP 协议是一种面向连接的，可靠的，基于字节流的传输层协议。TCP 作为一个比较基础的通信协议，有很多重要的机制保证了 TCP 协议的可靠性和健壮性。比如：使用序列号进行 TCP 报文段的排序和判重；使用校验进行报文段的错误检测；使用确认和重传定时器进行丢包重传；流量控制，避免发送方发送数据过快而接收方接受不过来；拥塞控制，避免网络拥塞。

HTTP 请求的 7 种方法

Get：只读请求，请求处理过程中不应该产生副作用，即 web 应用不应该因为 get 请求而发生任何状态改变。

Head：和 get 方法一样，但是只返回响应头。

Post：提交请求。

Put：上传请求。

Delete：删除 URL 标识的资源。

Trace：回显服务器收到的请求，用于测试或者诊断。

Options：请求服务器返回支持的所有 HTTP 请求方法，用于测试服务器是否正常。

HTTP 协议版本

1.0：1996 年发布，客户端和服务器之间交换的每个请求/响应都会创建一个新的 TCP 连接，会产生延迟。

1.1：加入了保持连接的概念来解决这个问题，降低了很多建立连接的开销。但是这个连接不能并发处理多个请求。

2.0：引入了 HTTP 流的概念，允许将多个不同的 HTTP 并发地复用同一个 TCP 连接，使得浏览器更高效地复用 TCP 连接。但是，TCP 并不理解 HTTP 流，当多个 HTTP 请求复用一个 TCP 连接，如果前面的请求/响应没有处理完，后面的请求/响应也无法处理，也就是会出现队头阻塞的现象。

3.0：使用 QUIC 的传输协议。协议在传输层把流当作一等公民来看待。多个 QUIC 流共享相同的 QUIC 连接，因此不需要额外的握手和慢启动来创建新的 QUIC 流。QUIC 流是独立的，其中一个流的丢包不会影响其他流。

BIO Blocking I/O 阻塞 I/O

进行 I/O 操作时，用户线程会一直阻塞，直到读操作或者写操作完成。

Socket 接收数据，操作系统内核处理过程

非阻塞 I/O（Non-Blocking I/O）

I/O 操作立即返回，发起线程不会阻塞等待。

非阻塞 read：

1）Socket 接收缓冲区有数据，读 n 个（不保证数据被读完整，因此可能要读多次）

2）Socket 接收缓冲区没数据，则返回失败（不会等待）

非阻塞 write

1）Socket 发送缓冲区满，返回失败（不会等待）

2）Socket 发送缓冲区不满，写 n 个数据（不保证一次性全部写入，因此可能要多次写）

Select（poll）管理下的 read 过程

主要是通过遍历所有 socket 的方式。缺点是 socket 数量多时，遍历成本很高，拷贝成本也高。

epoll 管理下的 read 过程

数据库架构

连接器：数据库连接器会为每个连接请求分配一块专用的内存空间用于会话上下文管理。建立连接对于数据库而言相对比较重，需要花费一定的时间。

语义分析与优化器：将各种复杂嵌套的 SQL 进行语义等价转换，得到有限几种关系代数计算结构，并利用索引等信息进一步进行优化。

为什么 PrepareStatement 更好

PrepareStatement 会预先提交带占位符的 SQL 到数据库进行预处理，提前生成好执行计划，当给定占位符参数，真正执行 SQL 的时候，执行引擎可以直接执行，效率更好。另外，PrepareStatement 可以防 SQL 注入。

数据库事务日志

进行事务操作时，事务日志文件会记录更新前 数据记录，然后再更新数据库中的记录，如果全部记录都更新成功，那么事务正常结束，如果过程中某条记录更新失败，那么整个事务全部回滚，以及更新的记录根据事务日志中记录的数据进行恢复，这样全部数据都恢复到事务提交前的状态，仍然保持数据一致性。

LSN：一个按时间顺序分配的唯一事务记录日志序列号。

TransID：产生操作的事务 ID。

PageID：被修改的数据再磁盘上的位置。

PrevLSN：同一个事务产生的上一条日志记录的指针。

UNDO：取消本次操作的方法，按照此方法回滚。

REDO：重复本次操作的方法。