总结

用户头像
chenzt
关注
发布于: 2020 年 07 月 29 日

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

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

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

2.NP问题

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

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

NP ?= P

NP-hard:比NP问题更难的问题

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

3.数组

创建数组需要一个连续的内存空间。数组中必须存放相同的数据类型。随机快速读写是数组的一个重要特性,根据数组下标访问数据,时间复杂度为O(1)

4.链表

链表可以使用零散的内存空间存储数据。所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针,要想在链表中查找一个数据,只能遍历链表,复杂度为O(N)

4.Hash表

hash表示根据关键码值而直接进行数据访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。

hash表key冲突解决:开放寻址、链地址法、再哈希法、建立公共溢出区

5.栈

数组和链表都被称为线性表。

栈是在线性表的基础上加了操作限制条件:后进先出。

6.队列

队列也是一种操作受限的线性表,栈是后进先出,队列是先进先出。阻塞等待的线程被放入队列。

应用场景:生产者消费者

7.树

树是一种抽象数据类型或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合

二叉排序树:

左子树上所有节点的值均小于或等于它的根节点的值。右子树上所有节点的值均大于或等于它的根节点的值。左右子树也分别为二叉排序树。

平衡的二叉排序树:

从任何一个节点出发,左右子树深度之差的绝对值不超过1,左右子树仍然为平衡二叉树。

红黑排序树:

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

根节点是黑色的

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

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

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

增删节点的时候,红黑树通过染色和旋转,保持红黑树满足定义



红黑树和平衡二叉树

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

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

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

8.跳表

跳表是一种随机化的数据结构,实现原理简单。



9网络通信协议

OSI七层模型:

应用层、表示层、会话层、传输层、网络层、数据链路层、物理层

TCP/IP四层模型:

应用层、传输层、网络层、链路层

网络数据包格式:

物理层:

物理层负责数据的物理传输。计算机输入输出的只能是0,1这样的二进制数据,但是在真正的铜线线路里有光纤、电缆、无线各种设备。光信号和电信号,以及无线电磁信号在物理上完全不同,如何让着些不同的设备能够理解、处理相同的二进制数据,是物理层要解决的问题。

链路层:

链路层就是将数据进行封装后交给物理层进行传输,主要就是将数据封装成数据帧,以帧为单位通过物理层进行通信,有了帧,就可以在帧上进行数据校验,进行流浪控制。链路层会定义帧的大小,这个大小被称为最大传输单元。

网络层:

网络层IP协议使得互联网应用根据IP地址就能访问到目标服务器,请求离开App后,到达运营服务商的交换机,交换机会根据这个IP地址进行路由转发,可能中间会经过很多个转发节点,最后数据到达目标服务器。

网络层的数据需要渐层链路层进行处理,而链路层帧的大小定义了最大传输单元,网络层的IP数据包必须要小于最大传输单元才能进行网络传出,这个数据包也有一个IP头,主要包括的就是发送者和接受者的IP地址。

传输层(TCP协议):

IP协议不是一个可靠的通信协议,不会建立稳定的通信链路,并不会确保数据一定送达。要保证通信的稳定可靠,需要传输层协议TCP。

TCP协议是一种面向连接的,可靠的、基于字节流的传输协议。TCP作为一个比较基础的通信协议,有很多重要的机制保证了TCP协议的可靠性和强壮行:

使用序号,对收到的TCP报文段进行排序和检测重复的数据。

无错传输,使用校验和检测报文段的错误。

使用确认和计时器来检测和纠正丢包或者延时。

流量控制,避免主机分组发送得过快而使接收方来不及完全收下。

拥塞控制,发送方根据网络承载情况控制分组的发送量,以获得更高性能同时避免拥塞崩溃。

丢包的重传



TCP建立连接的3次握手过程:

1.App先发送SYN=1,Seq=X的报文,表示请求建立连接,X是一个随机数。

2.服务器接收到这个报文后,应答SYN=1,ACK=X+1,Seq=Y的报文,表示同意建立连接。

3.App收到这个报文后,检查ACK的值为自己发送的Seq值+1,确认建立连接,并发送ACK=Y+1的报文给服务器;服务器收到这个报文后检查ACK值为自己发送的Seq值+1,确认建立连接。至此,App和服务器建立起TCP连接,就可以进行数据传输了。



TCP关闭连接4次挥手:

1.客户端向服务器发送一个FIN,请求关闭数据传输。

2.当服务器接收到客户端的FIN时,向客户端发送一个ACK,其中ACK的值等于FIN+SEQ

3.服务器向客户端发送一个FIN,告诉客户端应用程序关闭。

4.当客户端收到服务器端的FIN时,回复一个ACK给服务器端,其中ACK的值等于FIN+SEQ



应用层HTTP协议:

互联网应用需要在全球范围为用户提供服务,将全球的应用和全球的用户联系在一起,需要一个统一的应用层协议,这个协议就是HTTP协议。

HTTP请求的7种方法:

GET:只读请求,请求处理过程不应该产生副作用,即web应用不应该因为get请求而发生任何状态改变。

HEAD:和get方法一样,但是只返回响应头。

POST:提交请求

PUT:上传请求

DELETE:删除URL标识的资源

TRACE:回显服务器收到的请求,用以测试或者诊断。

Options:请求服务器返回支持的所有HTTP请求方法,测试服务器是否正常。



HTTP响应的5种状态

1XX消息:请求已被服务器接收,继续处理。

2xx成功:请求已成功被服务器接收、理解、并接受。

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

4XX请求错误:请求含有此法错误或者无法被执行

5XX服务器错误:服务器在处理某个正确请求时发生错误



HTTP协议版本:

HTTP/1.0,客户端请求到资源后会关闭连接,并发量大的时候会导致频繁创建、关闭TCP连接,而TCP三次握手、四次挥手会消耗一定的时间。

HTTP/1.1默认启用长连接模式,即客户端可以使用同一个TCP连接顺序发送多个请求,新版本也引入了管道机制,客户端可以不用等上一个请求的响应结果就可以发送下一个请求,但是服务器端也是按照客户端请求的顺序进行响应的,可以理解为半双工模式。

HTTP/2服务TCP连接的方式不同,依然遵循请求-响应模式,但客户端发送多个请求和服务端给出多个响应的顺序不受限制,这样既避免了队头堵塞,又能更快获取响应。



10.非阻塞网络I/O

阻塞I/O:进行I/O操作时,用户线程会一直阻塞,直到读操作或者写操作完成。

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

非阻塞read操作:socket接收缓冲区有数据,读n个。socket接收缓冲区没数据,则返回失败。

非阻塞write:socket发送缓冲区满,返回失败。socket发送缓冲区不满,写n个数据



11.系统I/O复用方式:select,poll,epoll

I/O 多路复用机制,单个线程通过记录跟踪每一个Socket (I/O流)的状态来同时管理多个 I/O 流



用户头像

chenzt

关注

还未添加个人签名 2018.05.15 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
作业请添加“极客大学架构师训练营”,便于分类
2020 年 07 月 29 日 17:46
回复
没有更多了
总结