第 08 周 优化系统性能 -02 学习总结

数据结构与算法

1. 时间复杂度

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

1. 空间复杂度

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

1. NP 问题

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

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

- NP ?= P

- NP-hard 问题:比 NP 问题更难的问题(NP 问题的解法可以规约到 NP-hard 问题的解法)

- NP 完全问题:是一个 NP-hard 问题,也是一个 NP 问题

1. 数据结构

- 数组

- 特性 :

- 内存创建连续空间

- 必须存放相同的数据

- 随机快速读写数组

- 时间复杂度 : 为 O(1)

- 链表

- 特点 :

- 可以使用零散的存储空间存储数据

- 每个元素阿斗必须包含一个指向下一个数据元素的内存地址指针

- 查找一个数据只能遍历链表

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

- 时间复杂度 : O(N)

- Hash 表

- 特点

- 快速访问数据

- 快速增删数据

- 时间复杂度

- O(1)

- Hash 冲突

- 栈

- 特点 :

- 后进先出

- 时间复杂度 :

- 队列

- 特点 :

- 先进先出

- 应用

- 搜索好友中关系最近的有钱人

- 搜索最短路径

- 树

- 特点

- 多个子树

-

- 应用

- 二叉排序树

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

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

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

- 时间复杂度

- O(logN)

- 平衡二叉(排序)树

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

- 左右子树仍然为平衡二叉树

- 旋转二叉树恢复平衡

- 插入时,最多只需要两次旋转就会重新恢复平衡.删除时,需要维护从被删节点到根节点这条路径上所有节点的平衡性,时间复杂度

O(logN)

- 红黑(排序)树

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

- 根节点是黑色的。

- 每个叶子节点(NULL)都是黑色的空节点。

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

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

- 跳表

1. 链表与数据对比.

- 频繁增删数据用链表

- 频繁查找多用数组

- 数组链表结合,实现快速査找和快速增删

- 数组做索引,存储链表

1. 红黑树 VS 平衡二叉树

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

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

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

1. 常用算法

- 穷举算法

- 递归算法

- 贪心算法

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

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

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

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

4.计算最终路径

- 动态规划

网络

1. web 请求的一次网络通讯历程

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

1. HTTP 响应的 5 种状态

- 1x 消息一一请求已被服务器接收,继续处理

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

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

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

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

1. Http 协议版本

- HTTP/1.0

- 一次通讯

- HTTP/1.1

- 长链接

- HTTP/2

- 复用 TCP

- HTTP/3

- QUIC

1. 阻塞 I/O

- 进行 WO 操作时,用户线程会一直阻塞,直到读操作或者写操作完成

1. 非阻塞 I/O

- I/O 操作立即返回,发起线程不会阻塞等待.

- 非阻塞 read 操作

- Socket 接收缓冲区有数据,读 n 个(不保证数据被读完整,因此有可能需要多次读)。

- Socket 接收缓冲区没数据,则返回失败(不会等待

- 非阻塞 wite:

- Socket 发送缓冲区满,返回失败(不会等待)。

- Socket 发送缓冲区不满,写 n 个数据(不保证一次性全部写入,因此可能需要多次写)

1. 系统 I/O 复用方式

- select

- poll

- epoll

数据库架构原理

1. 数据库架构

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

1. PrepareStatement 预编译

- 提前生成执行计划

- 防止 SQL 注入攻击

1. 聚簇索引

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

- MysαL 数据库的主键就是聚簇索引,主键 ID 和所在的记录行存储在一个 B+树中

1. 非聚簇索引

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

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

1. 要合理使用索引

- alter 消耗时间长

- alter 操作期间,全部阻塞

数据库事务

1. 事务特性 ACID

- 原子性( Atomicity!y):事务要么全部完成,要么全部取消。如果事务崩溃,状态回到事

务之前(事务回滚)。

- 隔离性( Isolation):如果 2 个事务 T1 和 T2 同时运行,事务 T1 和 T2 最终的结果是相

同的,不管 T1 和 T2 谁先结束,隔离性主要依靠锁实现。

- 持久性( Durability):一旦事务提交,不管发生什么(崩溃或者出错),数据要保存在

数据库中。

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

1. 数据库事务日志