架构师训练营第八周学习总结

数据结构

1.时间复杂度

执行的次数，表示为O(n)

多项式时间复杂度：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长

包括 O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n2) （平方阶）、O(n3)（立方阶）。

非多项式时间复杂度：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。

包括 O(2n)（指数阶）、O(n!)（阶乘阶）



2.空间复杂度

临时占用存储空间的大小，表示为O(n)



3.常用数据结构

• 数组

连续空间存储，随机快速读写，下标查找时间复杂度O(1)

• 链表

不连续的内存空间，增删数据方便,查找的时间复杂读O(n)

数组+链表实现快速查找和快速增删；例如通讯录(首字母分组+联系人)

• Hash表：快速查找+快速增删

Hash表key冲突解决：链表、红黑树

• 栈：后进现出；线程栈

• 队列：先进先出；生产者消费者

队列应用

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

搜索最短路径

• 树

1).二叉排序树：一般情况查询效率比链表结构要高；平均检索时间就能达到O(logn)，最坏时间可能达到O(n)

(1)若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

(2)若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

(3)左、右子树也分别为二叉排序树；

(4)没有键值相等的结点。

2).平衡二叉排序树

它或者为空树，或者其左右子树都是平衡二叉排序树，而且其左右的子数高度之差绝对值不超过1

查找平均复杂度是O（log(n)）

在每一次树插入新元素后，树的平衡都可能被破坏，需要旋转调整树的高度，以达到平衡树结构.

由于维护这种高度平衡所付出的代价（时间复杂度），更多的地方是用追求局部而不是非常严格整体平衡的红黑树

3).红黑排序树

(1)每个节点要么是黑色，要么是红色。

(2)根节点是黑色。

(3)每个叶子节点（NIL）是黑色。

(4)每个红色结点的两个子结点一定都是黑色。

(5)任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

在大量增删情况下效率更高（最多3次旋转恢复平衡，时间复杂度O(1)）

10.跳表



跳表的查询时间复杂度可以达到O(logn)

算法

1.穷举算法

2.递归算法

要有退出函数

时间复杂度:n*log(n)

3.贪心算法

局部最优解

迪杰斯特拉算法(最短路径):按长度递增的次序产生最短路径。即每次对所有可见点的路径长度进行排序后，选择一条最短的路径

4.动态规划

把大问题分解成子问题进行求解，也就是分治的思想

5.遗传算法

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

网络通信协议

物理层

0，1二进制数据传输

数据链路层：

数据封装为帧，及在帧上进行数据校验

数据链路层负载均衡：

网络层：

IP协议：不可靠的通信协议，不保证数据一定到达

传输层

TCP协议

三次握手

四次挥手

应用层

Http协议

版本：

1.0:每个TCP连接只能发送一个请求，发送数据完毕，连接就关闭，如果还要请求其他资源，就必须再新建一个连接

1.1: 引入了持久连接;对于同一个域名，大多数浏览器允许同时建立6个持久连接引入了管道机制，即在同一个TCP连接里，客户端可以同时发送多个请求;同一个TCP连接里，所有的数据通信是按次序进行的（半双工模式）。服务器只能顺序处理回应，前面的回应慢，会有许多请求排队，造成"队头堵塞"

2.0: 复用TCP连接，多个http复用一个tcp；多个http复用一个tcp时也是顺序处理

3.0: QUIC协议；QUIC包封装在UDP数据包中

非阻塞网络IO

BIO：进行IO操作时，用户线程阻塞

NIO，立即返回，不阻塞；线程轮询



poll(select)

需要遍历所有Socket

epoll

FDlist取数据，不需要遍历所有Socket

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

1.数据库架构

连接器：

初始化专门内存空间，用于上下文管理；建立连接较重，使用连接池复用连接；

语法分析器：

将sql->语法树

语义分析与优化器

sql语义等价优化；利用索引等信息进一步优化

执行计划;Explain

2.PreStatement

提交带占位符的SQL到数据库进行预处理，提前生成执行计划；真正执行的时候可以直接执行

可以防止SQL注入攻击

3.B+树

构建索引

4.聚簇索引

Mysql主键是聚簇索引，主键ID和所在记录行存储在一个B+树中

非聚簇索引

在叶子节点记录的是主键，

5.SQL优化

合理使用索引；

添加索引会阻塞写操作，连接不释放，也会影响读操作；

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

6.数据库事务

ACID

数据库事务日志



资料:

在线坐标系：

https://www.desmos.com/calculator