架构师训练营 -week8- 学习总结

时间复杂度与空间复杂度

时间复杂度

不是计算程序具体运行的时间，而是算法执行语句的次数。

多项式时间复杂度

O(1)，O(log(n))，O(n^a)等

非多项式时间复杂度

O(a^n)，O(n!)等

空间复杂度

一个算法在运行过程种临时占用存储空间大小的量度。

复杂度大小比较与估算

O(1)<O(log n)<O(n)<O(nlog(n))<O(n^a)<O(n!)

对复杂度的估算，通常用比较法，分析出极限值，用极限值与常见复杂度进行比较，最小的最大值即为该算法的时间或空间复杂度。

NP问题

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

NP问题：能在多项时间复杂度内验证答案正确与否的问题。【NP？=P有争议】

NP-hard问题：比NP问题更难的问题（NP问题的解法可以归约到NP-hard问题的解法，比如二元一次方程与一元一次方程。）

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

数据结构

数组

创建数组必须要内存种一块连续的空间。数组中必须存放相同的数据类型。

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

链表

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

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

要在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度为O(n)，插入数据的时间复杂度为O(1)。

单链表：单向查找，只有next，最后一个next指向null。

双链表：双向查找，有prev与next，最后一个next指向null。

环：next指向头节点。

数组与链表结合，可实现快速查找和快速增删。

Hash表

本质是个数组，将key取哈希值再计算对应的索引作为下标。插入数据与查找数据的时间复杂度都为O(1)。

出现Hash冲突时，索引对应的地址将带着链表。

栈

数组和链表都被称为线性表。在线性表的基础上加了”后进先出“的操作限制条件，就成了栈。

线程栈：正在运行的代码在栈顶；所以如果递归函数中没有跳出递归的条件，则会出现StackOverFlow的错误。

队列

在线性表的基础上加了”先进先出“的操作限制条件，就成了队列。

经典场景：生产者消费者；阻塞等待的线程被放入队列（等待获取重量级锁的线程）；搜索最短路径。

树

有一个prev，多个next的就会构成树。

二叉排序树

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

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

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

平衡的二叉排序树，查找时间复杂度O(logn)。

不平衡的二叉排序树，则不一定，极端情况会退化成链表。

平衡二叉（排序）树

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

左右子树仍然为平衡二叉树。查找时间复杂度O(logn)。

当平衡二叉树不平衡时，将旋转二叉树恢复平衡。

插入时，最多需要2次旋转就会重新恢复平衡，时间复杂度为O(1)。

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

红黑（排序）树

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

根节点是黑色的。

每个叶子节点都是黑色的空节点。

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

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

删除节点时，红黑树通过染色和旋转，保持红黑树满足定义。时间复杂度为O(1).

红黑树VS平衡二叉树

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

跳表

本质是有序的链表，查询与插入的时间复杂度为O(logn)。

优点：代码更容易实现，删除节点时，不需要维护树的平衡。

常用算法

穷举算法

典型场景：背包问题。时间复杂度是O(n!)

规模大的数据（大于1000），则几乎是无解的。

递归算法

经典算法：快速排序算法；输出斐波那契数列

时间复杂度是O(nlog(n))

没有退出条件时，会导致栈溢出。

贪心算法

典型场景：背包问题。

每一步都找最优解，最终结果不一定是最优解。

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

核心是找到起点到每个节点的最快路径。

动态规划

通过找到合适的角度，将所求解的目标值在某（几）个维度上展开，将一个大问题拆解为若干的小问题，小问题的最优解，寻找大问题的最优解。时间复杂度为O(n^2)或O(n)，决定因素为状态转移方程。

每个动态规划算法都是从一个网格开始。

动态规划将问题从上而下细化分解，从下往上计算结果。

遗传算法（Genetic Algorithm,GA)

例子场景：背包问题。

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

遗传算法以一种群体中的所有个体作为对象，并例用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和编译构成了遗传算法的遗传操作；

参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

在经过适应度函数筛选后，需要再经过一轮选择算法，决定可以遗传下去的染色体以及繁殖次数，以用于后续的交叉遗传阶段。

时间复杂度由适应度函数决定。遗传算法得到的不是最优解。

算法过程流程图

选择算法

轮盘赌算法（Roulette Wheel Selection)：是一种回放式随机采样方法，每个染色体进入下一代的概率等于它的适应度值与整体适应度值和的比例。

随机竞争选择（Stochastic Tournament)：每次按轮盘赌选择一对个体，然后让这两个个体进行竞争，适应度高的被选中，如此反复，直到选满为止。（Q:竞争失败个体是否进入下一轮轮盘赌？）

均匀排序：对群体中的所有个体按期适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。

网络通信协议

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

OSI模型：Open System Interconnection Reference Model，开放式系统互联通信参考模型。

网络数据包格式

网络层IP协议

该协议包装了源地址与目标地址。

不是一个可靠的通信协议，不会建立稳定的通信链路，并不会确保数据一定到达。

传输层TCP协议

使用以下机制保证TCP协议的可靠性和强壮性：

• 使用序号，对收到的TCP报文段进行排序和检测重复的数据。

• 无错传输，使用校验和检测报文段的错误。

• 使用确认和计时器来检测和纠正丢包或延时。

• 流量控制，避免主机分组发送得过快而使接收方来不及完全收下。

• 拥堵控制，发送方根据网络承载情况控制分组的发送量，以获得高性能同时避免拥塞崩溃。

• 丢失包的重传。

TCP建立连接需要进行3次握手

TCP关闭连接需要进行4次挥手

应用层HTTP协议

请求的7种方法

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

HEAD: 和GET方法一样，但只返回响应头。

POST: 提交请求。

PUT: 上传请求。

DELETE: 删除URL标识的资源。

TRACE: 回显服务器收到的请求，用以测试或者诊断。

OPTIONS: 请求服务器返回支持的所有HTTP请求方法，测试服务器是否正常。

响应的5种状态

1XX消息：请求已被服务器接收，继续处理。

2XX成功：请求已被成功服务器接收、理解、并接受。

3XX重定向：需要后续操作才能完成这一请求。

4XX请求错误：请求含有此法错误或者无法被执行。

5XX服务器错误：服务器在某个正确请求时发生错误。

协议版本

HTTP/1.0 客户端请求到资源会关闭连接，并发量大的时候会导致频繁创建、关闭TCP连接，而TCP三次握手、四次挥手会消耗一定的时间。

HTTP/1.1 默认启用长连接模式，即客户端可以使用同一个TCP连接顺序发送多个请求，新版本也引入了管道机制，客户端可以不用等上一个请求的响应结果就可以发送下一个请求，但是服务器端也时按照客户端请求的顺序进行响应，可以理解为半双工模式。

HTTP/2 复用TCP连接的方式不同，依然遵循请求-响应模式，单个TCP连接的使用效率提高了。但是，当多个HTTP请求复用一个TCP连接时，如果前面的请求/响应没有处理完，后面的请求/响应也无法处理，还是会出现队头堵塞的现象。

HTTP/3 不用TCP作为会话输层，而是使用QUIC（一中心的互联网传输协议）。该协议在传输层将流作为一等公民引入。多个QUIC流共享相同的QUIC连接，因此不需要额外的握手和慢启动来创建新的QUIC流。但QUIC流是独立的，且QUIC数据包封装在UDP数据包种，因此在大多数情况下，只影响一个流的丢包不会影响其他流。

阻塞I/O

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

非阻塞I/O

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

非阻塞read操作：

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

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

非阻塞write操作：

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

socket发送缓冲区不满，写n个数据（不保证数据被一次完整写入，可能需要多次写）

Java NIO

三大核心部分：Channel（通道）、Buffer（缓冲区）、 Selector（选择器）

数据总是从Channel读到Buffer中，或者从Buffer写到Channel中。Selector用于监听多个Channel的事件。（比如：连接打开，数据达到）。

epoll bug：https://blog.csdn.net/hemeinvyiqiluoben/article/details/82941571

数据库架构原理

数据库架构

连接器

会为每个连接请求分配一块专用的内存空间用于会话上下文管理。建立连接对数据库而言相对比较中，需要花费一定的时间。因此应用程序启动的时候，通常会初始化建立一些数据库连接放在连接池里，这样当处理外部请求执行SQL操作的时候，就不需要花费时间建立连接了。

语法分析器

将SQL语句解释成一棵语法树。

语义分析与优化器

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

执行计划

数据库选择消耗资源最小的那个方案，最终执行的计划。

预编译PreapareStatement

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

可以防止SQL注入攻击。

B+树

主要用于构建索引。

数据主要存放在叶子节点。

是一棵有序树。

聚簇索引

聚簇索引的数据库记录和索引存储在一起。

MySQL数据库的逐渐就是聚簇索引，主键ID和所在行存储在一个B+树中。

非聚簇索引

非聚簇索引在叶子节点记录的不是数据行记录，而是聚簇索引，也就是主键。

通过非聚簇索引找到主键索引，再通过主键索引找到行记录的过程也被称为回表。

优化查询

添加必要的索引。

仅对必要的字段添加索引。

使用更小的数据类型创建索引：int（4字节），timestamp（4字节）datetime（8字节）

数据库事务

ACID：原子性、隔离性、持久性、一致性。

数据库事务日志

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

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

TransID：产生操作的事务ID。

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

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

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

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