数据结构与算法

时间复杂度与空间复杂度

时间复杂度：算法执行语句的次数

空间复杂度：算法在执行过程中临时占用存储空间大小的量度

NP 问题

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

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

NP ?= P



例子：数独

常见数据结构

数组

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

链表

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

数组与链表对比

• 链表中增删数据要比数组性能好；

• 可以利用数组链表结合，实现快速查找和快速增删

哈希表

• 既能快速访问数据，又能快速增删数据；

• 日常开发中最常用的数据结构

哈希冲突：由于 key 经过哈希函数的结果是一致的，因此指向的地址相同，导致冲突

栈

在线性表（数组和链表）的基础上加了操作限制：后添加的数据，在删除时必须先删除，即“后进先出”。

注意：理解线程调用栈。

队列

一种操作受限的线性表；先进先出。

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

树

二叉排序树：左子树所有结点的值均小于或等于它的根结点的值；右子树上所有结点的值均大于或等于它的根节点的值。左、右子树也分别为二叉排序树。

不平衡的二叉排序树会退化成链表。

平衡二叉排序树：从任何一个节点出发，左右子树深度之差的绝对值不超过1.左右子树为平衡二叉树。

红黑树：

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

• 根节点是黑色的

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

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

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

红黑树 VS 平衡二叉树：

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

• 在大量增删的情况下，红黑树较好。

• 红黑树的平衡性不如平衡二叉树，查找效率较低。

跳表

常用算法

归类

• 穷举算法

• 递归算法

• 贪心算法

• 动态规划

递归算法

快排

贪心算法

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

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

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

3. 重复这个过程，直到对图中

网络通信协议

引入

web 请求的一次网络通信历程？



模型

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



TCP/ID 四层协议结构。



网络数据包格式



物理层

• 负责数据的物理传输

• 如何让不同的设备（光纤、电缆、无线）能够理解、处理相同的二进制数据，是物理层要解决的问题

链路层

• 将数据进行封装后给物理层进行传输

• 最大传输单元：定义帧的大小；帧中包含发送者和接受者的MAC地址（网卡的设备标识符，唯一）

网络层（IP 协议）

在传输给链路层的数据包中，加上IP地址，交换机通过IP地址进行路由转发，到达目标服务器

传输层（TCP 协议）

TCP协议：一种面向连接的、可靠的、基于字节流的传输层协议。

TCP 协议的三次握手与四次挥手：

三次握手：

1. APP->服务器：发送SYN=1 SEQ=X报文，表示建立连接，X为随机数。

2. 服务器->APP：应答SYN=1 ACK=X+1 SEQ=Y报文，表示同意建立连接。

3. APP：检查ACK正确性，发送ACK=Y+1 SEQ=Z报文，表示确认连接；服务器：检查ACK正确性，表示确认连接。



四次挥手

1. 客户端->服务器：发送FIN，请求关闭数据传输

2. 服务器->客户端：发送ACK=FIN+SEQ

3. 服务器->客户端：发送FIN，表示客户端应用程序关闭

4. 客户端->服务器：发送ACK=FIN+SEQ



应用层（HTTP 协议）

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

非阻塞网络 I/O

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

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

数据库架构

连接器 - 语法分析器 - 语义分析与优化器 - 执行引擎

连接器

• 为每个链接请求分配专用的内存空间，用于会话上下文管理。

• 建立连接成本较高，通常会初始化数据库连接在连接池中，当处理外部请求执行 SQL 操作时不需花费时间建立连接。

语法分析器

语法分析器只能检查出语句的大概错误位置。

语义分析与优化器

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

执行计划

通过 explain 分析 sql 语句：

• key：索引类型，NULL 无索引

• rows：需要处理的行数

• prossible_key：潜在可以利用的索引

PrepareStatement

String sql = "update User set name = ? where id = 1";
PreparedStatement ps = connection.prepareStatement(sql);
ps.setString(1,"xiaoyz");
ps.executeUpdate();

为什么PrepareStatement更好？

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

索引

B 树和 B+ 树



聚簇索引与非聚簇索引

• 聚簇索引（主键索引）：数据库记录和索引存储在一起

• 非聚簇索引（普通索引）：叶子节点存储的不是数据库记录，而是聚簇索引，即主键。

索引的使用

• 添加合适的索引提高性能

• 合理使用索引（不能盲目使用索引）

思考

• 善于思考，猜想比学一堆堆的知识更重要