数据结构与算法

时间复杂度与空间复杂度

• 时间复杂度

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

• O（2^n）表示对n数据处理需要进行2^n次计算

• O（1），O（log（n）），O（n^a）多项式时间复杂度

• O（a^n）和O（n！）非多项式时间复杂度

• 空间复杂度

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

• O（n）表示需要临时存储n个数据

NP问题

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

NP：能在多项式时间复杂度内验证答案正确与否的问题

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

• 解决一个NP-hard问题就可以解决一类NP问题

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

数组

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

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

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

链表

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

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

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

链表中增删数据要比数组性能好得多

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

Hash表

既快速访问数据，又快速增删数据

• 哈希表插入数据O（1），查找数据O（1）

• 为什么是O（1）？

• 计算hashcode取余得下标这个过程是O（1）

• hash表本质是一个指针类型的数组，数组在内存中是连续存储的，数组中每个元素都是一样的固定长度，故可以通过取得的下标快速访问，这个过程也是O（1）

• 常用且常见

Hash表key冲突

栈

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

栈就是在线性表的基础上加了这样的操作限制条件：

• 后面添加的数据，在删除的时候必须先删除——后进先出

线程运行时专有内存为什么被称为线程栈？

• 进程创建时会划分一个内存空间，进程里每个线程都有运行时专有内存

• 线程运行时专有内存存放的是函数的栈帧，函数的局部变量存放在函数的栈帧里面，每调用一个子函数或初始化一个局部变量，当前进行的就是调用的子函数或者正在初始化局部变量，等待子函数执行完毕或初始化局部变量后，子函数跳出或局部变量返回结果，继续执行父函数里的语句——这个执行过程符合后进先出的限制条件，所以被称为（线程）栈

线程调用栈

void f(){
int x = g(1);
x++; //g 函数返回，当前堆栈顶部为f函数栈帧，在当前栈帧继续执行f函数的代码
}
int g(int x){
return x + 1;
}



队列

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

典型应用场景：

• 生产者消费者；

• 阻塞等待的线程被放入队列。

• 例：锁只有一个，正在被队列外的线程使用中，若有新的线程请求锁，则该线程被放入队列中，当锁被释放，队头的阻塞线程出队列获得锁然后才能运行，即先请求先获得

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

概念：一级好友（你的好友）、二级好友（好友的好友）、...

• 首先“你”入队列，这时只有你自己在队列，这时“你”出队列

• 将一级好友BOB、ALICE、CLAIRE入队列

• 然后BOB出队列，看是不是有钱人，是有钱人则停止，如果不是有钱人，则将BOB的好友ANUJ、PEGGY入队列，这时ANUJ和PEGGY一定是排在ALICE和CLAIRE后面的

• 然后ALICE出队列，看是不是有钱人，是有钱人则停止，如果不是有钱人，则将ALICE的好友PEGGY入队列（入过就不入）

• 然后CLAIRE出队列，看是不是有钱人，是有钱人则停止，如果不是有钱人，则将其好友THON、JONNY入队列

• ......

由队列的先进先出限制可知，最后找到的一定是关系最近的有钱人

• 用队列搜索最短路径

每个节点入队列前检查是否已在队列中

• 首先0级节点起点CAB入队列，然后出队列，看是不是终点，不是则将一级节点CAT、CAR入队列

• CAT出队列，看是不是终点，不是则二级节点MAT、BAT入队列

• CAR出队列，看是不是终点，不是则二级节点BAR入队列

• MAT出队列，看是不是终点，不是则将节点BAR入队列（没入，已在队列）

• BAT出队列，看是不是终点，是，则结束。最短路径是CAB->CAT->BAT

二叉排序树

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

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

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

不平衡的二叉排序树

平衡二叉（排序）树

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

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

旋转二叉树恢复平衡

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

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



红黑（排序）树

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

• 根节点是黑色的。

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

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

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

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

红黑树VS平衡二叉树

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

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

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

跳表

牺牲更多的空间达到更少的时间完成查找

递归算法（快速排序）

def quicksort(array):
  if len(array)<2:
    return array // 基线条件：为空或只包含一个元素的数组是“有序”的
  else:
    pivot=array[0]// 递归条件
    less=[i for i in array[1:]if i <=pivot] // 由所有小于基准值的元素组成的子数组
    greater=[i for i in array[1:]if i>pivot] // 由所有大于基准值的元素组成的子数组
    return quicksort(less)+[pivot]+quicksort(greater)
print quicksort([10,5,2,3])

时间复杂度：n*log（n）

贪心算法

背包问题（典型NP问题）：小偷背了一个4磅的背包去商城偷东西，将哪类商品放入背包才能收益最大化。

每一步找到当前的最优解

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

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

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

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

4.计算最终路径。

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







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

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

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









遗传算法解决背包问题

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

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



问题：80公斤背包装哪些物品价值最大？

• 基因编码与染色体

• 物品基因编码

• 基因组合：染色体

• 选择初始染色体：随机产生（也可以人为或者算法选择）

适应函数与控制参数

• 选择适应度函数，这里选择为商品总价值

• 选择控制函数，这里为总重量

染色体101011超重，淘汰。

选择算法

在剩下的染色体中选择可以被遗传下去的染色体以及繁殖次数

100100,适应函数为60。

101010,适应函数为105。

010101,适应函数为140。

选择算法

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

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

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

交叉遗传

选择结果：101010和010101各繁殖两次

生产下一代：染色体交叉遗传

循环迭代，如果连续几代遗传都没有出现更强的染色体（价值总和更大）,那么算法收敛，当前最大价值的染色体为最终解。

有时候会在遗传过程中进行基因突变，得到基因突变染色体。

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

网络通信协议

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

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



网络数据包格式

物理层

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

链路层

链路层就是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流量控制。



链路层会定义帧的大小，这个大小也被称为最大传输单元。像HTTP要在传输的数据上添加一个HTTP头一样，数据链路层也会将封装好的帧添加一个帧头，帧头里记录的个重要信息就是发送者和接受者的MAC地址。MAC地址是网卡的设备标识符，是唯一的，数据帧通过这个信息确保数据送达到正确的目标机器。

数据链路层负载均衡

网络层

网络层IP协议使得互联网应用根据IP地址就能访问到目标服务器，请求离开App后，到达运营服务商的交换机，交换机会根据这个IP地址进行路由转发，可能中间会经过很多个转发节点，最后数据到达目标服务器。



网络层的数据需要交给链路层进行处理，而链路层帧的大小定义了最大传输单元，网络层的IP数据包必须要小于最大传输单元才能进行网络传输，这个数据包也有一个IP头，主要包括的就是发送者和接受者的IP地址。

IP负载均衡

传输层（TCP协议）

IP协议不是一个可靠的通信协议，不会建立稳定的通信链路，并不会确保数据一定送达。要保证通信的稳定可靠，需要传输层协议 TCP。

TCP协议是一种面向连接的、可靠的、基于字节流的传输层协议。TCP作为一个比较基础的通讯协议，有很多重要的机制保证了TCP协议的可靠性和强壮性：

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

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

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

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

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

• 丢失包的重传

TCP建立连接的3次握手过程

1.App先发送SYN=1,Seq=X的报文，表示请求建立连接，X是一个随机数；

2.服务器收到这个报文后，应答SYN=1,ACK=X+1,Seq=Y的报文，表示同意建立连接；

3.App收到这个报文后，检查ACK的值为自已发送的Seq值+1,确认建立连接，并发送ACK=Y+1的报文给服务器；服务器收到这个报文后检查ACK值为自己发送的Seq值+1,确认建立连接。至此，App和服务器建立起TCP连接，就可以进行数据传输了。

TCP关闭连接四次挥手

• 客户端向服务器端发送一个FIN,请求关闭数据传输。

• 当服务器接收到客户端的FIN时，向客户端发送一个ACK,其中ACK的值等于FIN+SEQ。

• 然后服务器向客户端发送一个FIN,告诉客户端应用程序关闭。

• 当客户端收到服务器端的FIN时，回复一个ACK给服务器端。其中ACK的值等于FIN+SEQ。

应用层HTTP协议

互联网应用需要在全球范围为用户提供服务，将全球的应用和全球的用户联系在一起，需要一个统一的应用层协议，这个协议就是HTTP协议。

HTTP 请求的7种方法

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

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

Post:提交请求。

Put:上传请求。

Delete:删除URL标识的资源。

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

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

HTTP 响应的5种状态

1xx消息--请求已被服务器接收，继续处理

2xx成功一一请求已成功被服务器接收、理解、并接受

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

4xx请求错误一一请求含有词法错误或者无法被执行

5xx服务器错误一一服务器在处理某个正确请求时发生错误

HTTP协议版本

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



HTTP/1.1试图引入保持连接的概念来解决这些问题，它允许客户端复用TCP连接，从而分摊了建立初始连接和针对多个请求缓慢启动的成本。但任意时点上每个连接只能执行一次请求/响应交换。

随着网络的发展，网站所需资源（CSS、JavaScript和图像等）不断增长，浏览器在获取和呈现网页时需要越来越多的并发性。但由于HTTP/1.1只允许客户端同时进行一次HTTP请求/响应交换，因此在网络层上获得并发能力的唯一方法是并行使用多个TCP连接。



HTTP/2引入了HTTP“流”的概念，允许将不同的HTTP并发地复用到同一TCP连接上，使浏览器更高效地复用TCP连接。HTTP/2解决了单个TCP连接的使用效率低的问题，现在可以通过同一连接同时传输多个请求/响应。但是，TCP并不理解HTTP流当多个HTTP请求复用一个TCP连接，如果前面的请求/响应没有处理完，后面的请求/响应也无法处理，也就是会出现队头堵塞现象。



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



非阻塞网络I/O

计算机之间如何进行网络请求？

Socket、端口

服务器-客户端

多线程服务器-客户端

线程池服务器

BIO Blocking I/O 阻塞I/O

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

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

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

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

• 非阻塞read操作：

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

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

• 非阻塞write:

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

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

Java NIO（New I/O）



系统I/O复用方式：select、poll、epoll

Select（poll）管理下的read过程

epoll管理下的read过程

无活动连接时，Selector.select方法被阻塞

数据库架构原理与性能优化

PrepareStatement预编译

statement.executeUpdate("UPDATE Users SET stateus = 2 WHERE userID=233");
PreparedStatement updateUser = con.prepareStatement("UPDATE Users SET
stateus = ? WHERE userID = 233");
updateUser.setInt(1, 2);
updateUser.executeUpdate();

数据库架构

连接器

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

语法分析器



select s_grade from staff where s_city not in (select p_city from proj where s_empname=p_pname)



mysql> explain select * from users whee id = 1;
ERROR 1064 (42000): You have an error in your SQL syntax; check the manual that
corresponds to your MySQL server version for the right syntax to use near 'id = 1' at line 1

语义分析与优化器

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

select f.id from orders f where f.user_id = (select id from users);
select f.id from orders f join users u on f.user_id=u.id;

执行计划

Key:索引类型，NULL无索引

Rows:需要处理的行数

Possible_keys:潜在可以利用的索引

为什么PrepareStatement更好

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

PrepareStatement 可以防止 SQL 注入攻击。

· select * from users where username = 'Frank';

· Frank';drop table users;--

· select * from users where username = 'Frank';drop table users;-';

select*from users where username=?;

B-树与B+树



聚簇索引

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

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

非聚族索引

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

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

添加必要的索引优化SQL查询性能

在几百万行的数据库中查找一个条记录，如果没有索引，就需要全表扫描，检索所有的行记录，才能找到需要的记录。

谨慎使用索引

不要盲目添加索引，尤其在生产环境中

• 添加索引的alter操作会消耗较长的时间（分钟级）

• Alter操作期间，所有数据库的增删改操作全部阻塞，对应用而言，因为连接不能释放，事实上，查询也被阻塞。

删除不用的索引，避免不必要的增删开销



使用更小的数据类型创建索引

• int4字节 bigint8字节，Timestamp4字节 Datetime8字节

数据库事务

事务特性 ACID

• 原子性（Atomicity):事务要么全部完成，要么全部取消。如果事务崩溃，状态回到事务之前（事务回滚）。

• 隔离性（lsolation):如果2个事务T1和T2同时运行，事务T1和T2最终的结果是相同的，不管T1和T2谁先结束，隔离性主要依靠锁实现。

• 持久性（Durability):一旦事务提交，不管发生什么（崩溃或者出错）,数据要保存在数据库中。

• 一致性（Consistency):只有合法的数据（依照关系约束和函数约束）才能写入数据库。

数据库事务日志

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



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

TransID:产生操作的事务ID。

PagelD:被修改的数据在磁盘上的位置。

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

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

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