第八周课程总结

一、数据结构与算法

1、时间复杂度和空间复杂度

2、NP 问题

P 问题

NP 问题

NP ?= P (NP 问题是不是就是 P 问题)

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

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

二、线性表数据结构

1、数组

结构：

• 内存中一块连续的空间

• 数据类型相同

特征：

• 随机快速读写，根据数组的下标访问数据，时间复杂度为 O(1)

2、链表

结构：

• 零散的内存空间存储数据

• 每个数据元素包含一个指向下一个数据元素的内存地址指针；

特性：

• 遍历链表来查找数据，时间复杂度是 O(N)

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

数组随机读取元素的性能好很多

数组链表结合，实现快速查找和快速增删，结构类似于 Hash 表

3、Hash 表

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

Hash 冲突

4、栈

数组和链表都是线性表

在线性表的基础上加上这样的操作限制：后进先出，则为栈

线程运行时专有内存即为线程栈

5、队列

队列也是一种操作受限的线性表，先进先出！

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

用队列搜索好友中关系最近的有钱人，如何实现？

对队列搜索最短路径

三、树

1、二叉树

1.1 二叉排序树

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

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

二叉排序树的查找的时间复杂度是 o(log2N)

不平衡的二叉排序树，如下

已经退化为一个链表了

1.2 平衡二叉排序树

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

每个左右子树自己任然为平衡二叉排序树

旋转二叉树 最多只需要两次旋转就会重新恢复平衡

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

2、红黑（排序）树

概念：

    每个节点只有两种颜色：

    根节点是黑色的

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

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

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

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

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

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

TreeMap 就是使用红黑树实现；

3、跳表

跳表的数据结构如下：

提升链表查询性能

但是空间复杂度比较高

四、常用的算法

1、穷举算法

2、递归算法

时间复杂度 n* log(n)

3、贪心算法

背包问题：小偷背了一个 4 磅背包去商城偷东西，将哪些商品放入背包才能收益最大化

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

算法描述：

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

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

3、重复这个逻辑，知道对图中的每个节点都这样做

4、计算最短路径

4、动态规划

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

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

5、遗传算法解决背包问题

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

五、网络通信协议

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

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

网络数据包格式

1、物理层

负责数据的物流传输

通信线路有光纤、电缆、无线和无线电磁信号等；

如何让这些不同的设备能够理解和处理相同的二进制数据，这是物理层要解决的问题

2、链路层

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

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

链路层实现负责均衡

IP 负载均衡

3、传输层

TCP 建立连接的三次握手过程：

TCP 关闭连接 4 次挥手

4、应用层 HTTP 协议

HTTP 请求的 7 种方法

Get

Head

Post

Put

Delete

Trace

Options

HTTP 响应的 5 种状态

1xx 消息

2xx 成功

3xx 重定向

4xx 请求错误

5xx 服务器错误

HTTP/1.0 — 客户端和服务器之间交换的每个请求/响应都会创建一个新的 TCP 连接，这意味着所有请求之前都需要进行 TCP 握手连接，因此所有请求都会产生延迟

HTTP/1.1 — 允许客户端复用 TCP 连接，从而分摊了简历初始连接和针对多个请求缓慢启动的成本，但任意时点上每个连接只能执行一次请求/响应交换

HTTP/2 —  HTTP 流的概念，允许将不同的 HTTP 并发地复用到同一个 TCP 连接上，使浏览器更高效地复用 TCP 连接。但是会出现队头阻塞想象

HTTP/3 —  使用 QUIC（一种新的互联网传输协议），数据包封装在 UDP 数据包内；

5、非阻塞网络 I/O

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

操作系统提供了编程接口 Socket

6、BIO Blocking I/O 

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

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

非阻塞 I/O

Java NIO(New I/O) 

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

六、数据库架构原理

1、数据库架构

1）连接器

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

2）语法分析器

3）语义分析与优化器

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

4）执行计划 explain

Key：索引类型，NULL 表示没有索引

Rows： 需要处理的行数

Possible_keys: 潜在可以利用的索引

2、索引

1）B+树结构的理解

2）聚簇索引

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

3）非聚簇索引

非聚簇索引在叶子节点记路的就不是数据行记录，而是聚簇索引，也就是主键，通过非聚簇索引找到主键索引，再通过主键索引找到行记录的过程也称作回表；

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

5）合理使用索引

• 添加索引的 alter 操作会消耗较长的时间

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

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

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

3、数据库事务

事务特性 ACID

• 原子性

• 隔离性

• 持久性

• 一致性

数据库通过事务日志来实现事务