数据结构与算法



时间复杂度与空间复杂度

时间复杂度

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

• O(2^n)    表示对n数据处理需要进行 2^n 次计算。

• O(1), O(log(n)), O(n^a) 多项式时间复杂度

• O(n^a) 和O(n!) 非多项式的时间复杂度。



空间复杂度

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

• O(n) 表示需要临时存储n个数据。



NP问题

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

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

• NP ?= P

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

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



数组

创建数组必须要内存中一块连续的空间。数组中必须存放相同的数据类型。随机快速读写是数组的一个重要特性，根据数组的下标访问数据，时间复杂度为 O(1).





链表

链表可以使用零散的内存空间存储数据。所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。要想在链表中查找一个数据，只能遍历链表，所以链表的查询时间复杂度总是O(N).





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

• 链表增删数据时间复杂度总是O(1).

• 数组增删数据时间复杂度总是O(N).



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

Hash 表

如何既快速访问数据，有快速增删数据？

Hash 冲突



如果Hash(Key)的位置，存储不止一个值，就挨个匹配key值，取出相应的value值。



栈

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



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



线程调用栈

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





队列

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

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



树





二叉排序树

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

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

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

时间复杂度：O(logn)



平衡二叉（排序）

树从任何一个结点出发，左右子树深度只差的绝对值不超过1.左右子树仍然为平衡二叉树。



旋转二叉树恢复平衡

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



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

右旋的过程：

1. 15变成根节点；

2. 17比15大，则17是15的右节点。

3. 16比17小，则16是17的左节点。



左旋的过程：

1. 25变成根节点；

2. 22比25小，则22是25的左节点。

3. 23比22大，则23是22的右节点。



红黑（排序）树

每个节点只有两种颜色：红色和黑色。根节点是黑色的。每个叶子节点(Null)都是黑色的空节点。从根节点到叶子节点，不会出现两个连续的红色节点。从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。



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



TreeMap就是用红黑树实现的。



红黑树 vs 平衡二叉树

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



跳表



时间复杂度：O(logn)

空间复杂度：O(n)



常用算法

• 穷举算法

• 递归算法

• 贪心算法

• 动态规划

递归算法（快速排序算法）

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])

注意：

递归算法一定要有退出条件，否则就会栈溢出 Stack Overflow.

栈的空间是有限的，所以函数调用不能太深，比如写个计数，超过1000就退出。



时间复杂度：O(n * log(n))



网络通信协议



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



客户端 >  域名访问 > DNS 解析为 IP地址 >

• 获取静态资源 jpg, css, javascript, 通过CDN

• 获取动态资源，基于TCP访问到负载均衡服务器 （比如订单、商品详情等）

反向代理服务器 > 负载均衡服务 > 网关服务器 > 微服务服务器 >

• 数据库服务器 （基于TCP协议访问 ）

• 缓存服务器（基于TCP协议访问 ）



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



1. 链路层（Mac地址），互联网有很多种媒介，比如光纤，网线等，要定义好什么是0，什么是1. 比如大于多少电压是1。

2. 网络互联层，根据Router路由选择找到目标服务器，根据迪杰斯特拉算法得到最短路径。

3. 传输层，主要看监听的端口，socket。

4. 应用层，把二进制返回给应用，应用需要反序列化为程序可识别的数据。HTTP协议。



• 应用层 HTTP

• 传承层 TCP/IP 协议

• 互联网 IP 数据

• 网络接口 Mac地址



每一层都包了一个头和数据，传到下一层。

解析的话，就是把头都脱掉，剩下的就是下一层的数据。



网络数据包格式



1. HTTP协议头，方法(POST), path, 编码(utf-8)

2. TCP 协议头，HTTP进程监听端口

3. IP协议头，服务器IP

4. 链路层协议头，服务器Mac地址



物理层

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

链路层

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



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



数据链路层负载均衡



负载均衡服务器直接改Mac地址，达到负载均衡。



网络层

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



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



IP负载均衡



负载均衡服务器通过修改IP地址，到达内网的应用服务器。



传输层(TCP协议)

IP 协议不是一个可靠的通信协议，不会建立稳定的通信链路，并不会确保数据一定送达。要保证通信的稳定可靠，需要传输层协议 TCP。TCP协议是一种面向连接的、可靠的、基于字节流的传输层协议。TCP作为一个比较基础的通讯协议，有很多重要的机制保证了 TCP 协议的可靠性和健壮性：使用序号，对收到的 TCP 报文段进行排序和检测重复的数据。无错传输，使用校验和检测报文段的错误。使用确认和计时器来检测和纠正丢包或者延迟。流量控制，避免主机分组发送得过快而使接收方来不及完全收下。拥塞控制，发送方根据网络承载情况控制分组的发送量，以获得高性能同时避免拥塞崩溃。丢失包的重传。



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

App 先发送 SYN=1， Seq=X 的报文，表示请求建立连接，X是一个随机数；服务器收到这个报文后，应答 SYN=1，ACK=X+1，Seq=Y 的报文，表示同意建立连接；App 收到这个报文后，检查 ACK 的值为自己发送的 Seq 值 +1，确认建立连接，并发送 ACK = Y + 1 的报文给服务器；服务器收到这个报文后检查 ACK 值为自己发送的 Seq值 + 1，确认建立连接。至此，App 和服务器建立 TCP 连接，就可以进行数据传输。



TCP 关闭连接4次挥手

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

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

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

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





应用层 HTTP 协议

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



HTTP请求的7种方法

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

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

3. Post：提交请求。

4. Put：上传请求。

5. Delete：删除URL标识的资源。

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

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



HTTP 响应的5种状态

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

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

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

• 4XX 请求错误 -- 请求含有词法错误或者无法被执行。

• 5XX 服务器错误 -- 服务器在处理某个正确请求时发生错误。



非阻塞网络 I/O

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

Socket、端口



服务器 -- 客户端



一共有两个Socket

1. 监听端口的Socket

2. 通信的时候又创建一个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 个数据（不保证一次性全部写入，因此可能需要多次写）。



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



Select (poll) 管理下的read过程





epoll 管理下的read 过程