架构师培训营第八周总结
一、NP问题
P:能在多项式时间复杂度内解决的问题
NP:能在多项式时间复杂度内验证答案正确与否的问题
二、数组
数组的查询时间复杂度为O(1)
三、链表
链表可以使用零散的内存空间存储数据
链表的查找时间复杂度为O(N)
增删数据比数组性能要好
四、栈
栈和数组一样,都是线性表
栈删除数据,是后进先出的原则
五、队列
队列跟栈相反,是先进先出
常用的MQ中间件,运用了队列的特性,而且可以保证按顺序消费
六、树
二叉排序树,左子树上所有结点的值均小于或等于它的根结点的值,右子树上所有结点的值均大于或等于它的根结点的值
平衡二叉树
红黑树,在增删节点的时候,通过染色和旋转,保持红黑树的特性
跳表,最常用的就是redis
七、常用的算法
穷举算法或暴力算法
递归算法
贪心算法-迪杰斯特拉算法
动态规划DP
广度优先或深度优先算法
遗传算法
八、OSI七层网络模型
应用层
表示层
会话层
传输层
网络层
数据链路层
物理层
九、TCP/IP四层模型
应用层
传输层
网络互联层
网络访问层
TCP3次握手
1)ACP先发送SYN=1,Seq=x的报文,表示请求建立连接,X是一个随机数;
2)服务器收到这个报文后,应答SYN=1,ACK=X+1,Seq=Y的报文,表示同意建立连接;
3)App收到这个报文后,检查ACK的值为自己发送的Seq值+1,确认建立连接,并发送ACK=Y+1的报文给服务器;服务器收到这个报文后检查ACK值为自己发送的Seq值+1,确认建立连接。
四次挥手
1)客户端向服务端发送一个FIN,请求关闭数据传输
2)当服务器接收到客户端的FIN时,向客户端发送一个ACK,其中ACK的值等于FIN+SEQ
3) 服务器向客户端发送一个FIN,告诉客户端应用程序关闭
4)当客户端收到服务器端的FIN 是,回复一个ACK给服务器端。其中ACK的值等于FIN+SEQ
十、应用层HTTP协议
HTTP请求的七种方法,Get,Head,Post,Put,Delete,Trace,Options
HTTP协议包图:
HTTP响应的5种状态,1xx消息--请求已被服务器接收,继续处理;2xx成功--请求已成功被服务器接收、理解、并接受;3xx重定向;4xx请求错误;5xx服务器错误
版权声明: 本文为 InfoQ 作者【talen】的原创文章。
原文链接:【http://xie.infoq.cn/article/9ed4e1cba706ea2720b72ac02】。未经作者许可,禁止转载。
评论