【第八周】学习总结——数据结构和算法，网络及数据库

本周主要学习内容包括数据结构和算法，网络，数据库。

数据结构和算法

算法复杂度分为时间复杂度和空间复杂度

时间复杂度：执行算法所需的计算次数度量

空间复杂度：执行算法所需的临时内存空间度量



NP问题

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

NP问题：不能确定是否能在多项式时间复杂度内解决问题，但能在多项式时间复杂度内验证的问题

NP？=P （世界七大数学难题，100万美元）

数据结构

• 数组，读写：O(1)



• 链表，查找：O(n)，增删性能比数组好

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

HashMap：是读写性能都非常不错且使用非常普遍的一种数组和链表的组合实现。



• 栈，后进先出

线程调用栈



• 队列，先进先出

生产者消费者，最短路径



• 树

二叉排序树，平衡二叉树（排序），红黑树（排序）

红黑树

红黑树最多只需3次旋转就能达到平衡，时间复杂度是O(1)。在大量增删的情况下，红黑树的效率更高。

红黑树的平衡性不如二叉树，查找效率会差些。



• 跳表

有序链表上面连接更稀松的链表作为索引

常用算法

穷举算法，

递归算法，快速排序算法，时间：O(n*log(n))，空间：O(log(n))

贪心算法，背包问题，迪杰斯特拉算法（快速路径）

动态规划，背包问题

遗传算法，背包问题，遗传算法不提供最优解

网络通信协议

互联网 - 内部网络



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



IP

IP协议不是一个可靠的通信协议，并不会保证数据一定送达。

TCP

TCP协议保证了数据通信的稳定可靠。

三次握手



四次挥手

HTTP

HTTP/1.0，短连接，并发量大时频繁创建和关闭TCP连接

HTTP/1.1，默认长连接，管道机制，可顺序并发，顺序返回

HTTP/2，多路复用，多请求并发，无顺序限制，避免“队头堵塞”（HTTP协议层面，非TCP层面）

HTTP/3，HTTP-over-QUIC，QUIC使用UDP协议

非阻塞网络IO

系统IO复用：select，poll，epoll

epoll管理下的read过程



数据库架构原理



执行计划：explain

JDBC：PrepareStatement，预编译，重复使用

B-树与B+树

索引：聚簇索引，非聚簇索引

事务特性ACID

事务日志记录更新前数据用于回滚

学习小结

以上知识属于架构师常识，必须熟练于心。