数据结构、算法、网络和 IO

 关注
发布于: 2020 年 07 月 28 日
数据结构和算法算法分析时间复杂度在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。
﻿
注：时间复杂度并不是计算程序具体运行时间，而是算法执行语句的次数
平均时间复杂度平均时间复杂度是指所有可能的输入实例均以等概率出现情况下该算法的运行时间。
最坏时间复杂度最坏情况下的时间复杂度称为最坏时间复杂度。通常都是讨论最坏时间复杂度的，因为这个保证了算法的运行时间不会比最坏情况更长。
常见的时间复杂度常数阶：O(1)
线性阶：O(n)
平方阶：O(n^2)
对数阶：O(logn)
nlogn阶：O(nlgon)
立方阶：O(n^3)
指数阶：O(2^n)
阶乘：O(n!)
﻿
常用的时间复杂度从小到大依次是：
O(1) < O(logn) < O(n) < O(nlogn) < O( n^2 ) < O( n^3 ) < O( 2^n ) < O( n! )< O( n^n )
﻿
不同时间复杂度的增长速度对比如下:
空间复杂度空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度
﻿
一个算法在计算机存储器上所占用的存储空间，包括
存储算法本身所占用的存储空间，存储算法本身所占用的存储空间由算法代码的书写长短有关，优化代码量可节约空间
算法的输入输出数据所占用的存储空间，算法的输入输出数据所占用空间，通常解决一个问题的不同算法的输入输出数据基本相同，因此不用考虑优化
算法在运行过程中临时占用的存储空间，算法在运行过程中临时占用的存储空间，例如有些算法通过数组解决，有些通过链表解决等，不同的算法占用的临时存储空间不同，需要关注优化
﻿
注：衡量一个算法的效率主要考虑时间复杂度，因为时间复杂度直接与用户体验相关，用可以用空间换取时间。
常见的空间复杂度空间复杂度比较常用的有：O(1)、O(n)、O(n²)
常用算法的时间和空间复杂度
NP问题P问题：一个问题可以在多项式（）的时间复杂度内解决。
NP问题：一个问题的解可以在多项式的时间内被验证。
NP-hard问题：任意np问题都可以在多项式时间内归约为该问题，但该问题本身不一定是NP问题。
NPC问题：既是NP问题，也是NP-hard问题。
常见的数据结构数组数组是一种在连续内存空间上存储相同类型数据的数据结构，可通过数组名和下标进行数据的访问和更新。数组的读写时间复杂度是O(1)。
﻿
链表链表是利用零散的内存空间存储数据的，每个数据节点都是由数据本身和下一个数据的地址指针组成，查询链表数据需要遍历链表，因此链表的读写数据的时间复杂度是O(n)。
﻿
数组和链表比较
﻿
Hash表哈希表是一种通过键值对直接访问数据的结构。散列表的实现原理是映射的原理，通过设定的一个关键字和一个映射函数，就可以直接获得访问数据的地址，实现O(1)的数据访问效率。
﻿
栈栈是一个后进先出的线性表，栈的常用操作包括入栈push和出栈pop。
﻿
队列队列是一个先进先出的线性表，队列的常用操作包括入队列offer、出队列poll
﻿
树树是以层次化方式组织和存放数据的特定数据结构。
﻿
关键概念结点：使用树结构存储的每一个数据元素都被称为“结点”。
根节点：树中的第一个节点就是根节点。
叶子节点：如果结点没有任何子结点，那么此结点称为叶子结点。
父结点：拥有叶子节点的节点是父节点。
结点的层次：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推。
树高：是由根结点出发，到子结点的最长路径长度。
结点深度：是指对应结点到根结点路径长度。
﻿
树的分类最常见的就是二叉树，二叉树(Binary Tree)是一个有根树，并且每个节点最多只有2科子树(即二叉树中不存在度大于2的结点)，并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树又分为完全二叉树、满二叉树、平衡二叉树、红黑树等。
﻿
完全二叉树
除了最后一层结点，其它层的结点数都达到了最大值；同时最后一层的结点都是按照从左到右依次排布
﻿
满二叉树
除了最后一层，其它层的结点都有两个子结点。
﻿
平衡二叉树
平衡二叉树是一棵二叉排序树，且具有以下性质：
是一棵空树或它的左右两个子树的高度差的绝对值不超过1，
左右两个子树都是一棵平衡二叉树
﻿
红黑树
红黑树是一种含有红黑结点并能自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。它必须满足下面性质：
﻿
每个节点要么是黑色，要么是红色。
根节点是黑色。
每个叶子节点（NIL）是黑色。
每个红色结点的两个子结点一定都是黑色。
任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
﻿
红黑树VS平衡二叉树：
﻿
跳表跳表是通过增加链表的多级索引来加快原始链表的查询效率。这样的方式可以让查询的时间复杂度从O(n)提升至O(logn)
﻿
常见的算法类型算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。直白的说就是能够对一定规范的输入，在有限时间内获得所要求的输出。
算法的特征有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止；
确切性（Definiteness）：算法的每一步骤必须有确切的定义；
输入项（Input）：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
输出项（Output）：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
可行性（Effectiveness）：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。
﻿
穷举算法穷举法又称穷举搜索法，是一种在问题域的解空间中对所有可能的解穷举搜索，并根据条件选择最优解的方法的总称
求解方法步骤：
确定枚举对象、枚举范围、判断条件。
循环验证每一个解。
﻿
递归算法递归算法就是在程序中不断反复调用自身来达到求解问题的方法。
分类函数的递归调用分两种情况:直接递归和间接递归。
直接递归，即在函数中调用函数本身。
间接递归，即间接地调用一个函数，如funca调用func b, func b又调用funca。
﻿
优缺点优点:程序代码更简洁清晰，可读性更好。
缺点:大部分递归例程没有明显地减少代码规模和节省内存空间。
﻿
应用场景使用递归需要具备两个条件：
子问题与原始问题为同样的事情，二者的求解方法是相同的，且子问题比原始问题更易求解。
递归不能无限制地调用本身，必须有个递归出口。递归出口对应的情形相对简单，可以化简为非递归状况处理。
﻿
贪心算法贪心算法可以获取到问题的局部最优解，不一定能获取到全局最优解，同时获取最优解的好坏要看贪心策略的选择。特点就是简单，能获取到局部最优解。
注：贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
###### 基本思路
建立数学模型来描述问题。
把求解的问题分成若干个子问题。
对每一子问题求解，得到子问题的局部最优解。
把子问题的解局部最优解合成原来解问题的一个解。
﻿
动态规划算法动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
动态规划要解决的是多阶段决策问题：
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
﻿
使用情况最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。有些子问题会被重复计算多次，动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
﻿
一般步骤分析最优解的性质，并刻划其结构特征。
递归地定义最优值。
以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
根据计算最优值时得到的信息，构造一个最优解。
﻿
两种形式自顶向下的备忘录法 
自底向上。
﻿
遗传算法遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
﻿
相关术语基因型(genotype)：性状染色体的内部表现；
表现型(phenotype)：染色体决定的性状的外部表现，或者说，根据基因型形成的个体的外部表现；
进化(evolution)：种群逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的。
适应度(fitness)：度量某个物种对于生存环境的适应程度。
选择(selection)：以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程。
复制(reproduction)：细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。
交叉(crossover)：两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交；
变异(mutation)：复制时可能（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状。
编码(coding)：DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射。
解码(decoding)：基因型到表现型的映射。
个体（individual）：指染色体带有特征的实体；
种群（population）：个体的集合，该集合内个体数称为种群的大小。       
﻿
算法过程
﻿
网络通信协议OSI七层模型和TCP/IP四层模型OSI七层模型OSI（Open System Interconnect），即开放式系统互联，OSI定义了网络互连的七层框架（物理层、数据链路层、网络层、传输层、会话层、表示层、应用层）。具体模型如下：
﻿
各个分层使用的协议
﻿
OSI七层和TCP/IP四层的关系OSI引入了服务、接口、协议、分层的概念；TCP/IP借鉴了OSI的这些概念建立TCP/IP模型。
OSI先有模型，后有协议，先有标准，后进行实践；而TCP/IP则相反，先有协议和应用再提出了模型，且是参照的OSI模型。
OSI是一种理论下的模型，而TCP/IP已被广泛使用，成为网络互联事实上的标准。
﻿
OSI七层和TCP/IP的区别TCP/IP他是一个协议簇；而OSI（开放系统互联）则是一个模型，且TCP/IP的开发时间在OSI之前。
TCP/IP是由一些交互性的模块做成的分层次的协议，其中每个模块提供特定的功能；OSi则指定了哪个功能是属于哪一层的。
TCP/IP是五层结构，而OSI是七层结构。OSI的最高三层在TCP中用应用层表示。
﻿
经典图例
﻿
TCP协议TCP协议，传输控制协议（英语：Transmission Control Protocol，缩写为 TCP）是一种面向连接的、可靠的、基于字节流的传输层通信协议，由IETF的RFC 793定义。
﻿
TCP通信需要经过创建连接、数据传送、终止连接三个步骤。
﻿
TCP通信是面向连接并且可靠的。通信双方在正式进行通信之前必须先建立可靠一对一的连接，并且分配一定的系统内核资源，双发的数据通过这个连接进行，而且当通信结束之后双发必须断开连接以释放系统资源。
﻿
TCP采用发送应答机制，每次传输的成功都依赖于发送和回应。如果在一定时间没有收到回应，则会进行重发。并且为了不丢包，每个数据包中都有一个序号，同时序号也保证了传送到接收端实体的包的按序接收。
﻿
TCP报文格式
﻿
序列号seq：占4个字节，用来标记数据段的顺序，TCP把连接中发送的所有数据字节都编上一个序号，第一个字节的编号由本地随机产生；给字节编上序号后，就给每一个报文段指派一个序号；序列号seq就是这个报文段中的第一个字节的数据编号。
确认号ack：占4个字节，期待收到对方下一个报文段的第一个数据字节的序号；序列号表示报文段携带数据的第一个字节的编号；而确认号指的是期望接收到下一个字节的编号；因此当前报文段最后一个字节的编号+1即为确认号。
确认ACK：占1位，仅当ACK=1时，确认号字段才有效。ACK=0时，确认号无效
同步SYN：连接建立时用于同步序号。当SYN=1，ACK=0时表示：这是一个连接请求报文段。若同意连接，则在响应报文段中使得SYN=1，ACK=1。因此，SYN=1表示这是一个连接请求，或连接接受报文。SYN这个标志位只有在TCP建产连接时才会被置1，握手完成后SYN标志位被置0。
终止FIN：用来释放一个连接。FIN=1表示：此报文段的发送方的数据已经发送完毕，并要求释放运输连接
﻿
PS：ACK、SYN和FIN这些大写的单词表示标志位，其值要么是1，要么是0；ack、seq小写的单词表示序号。
标志位标志位（Flags）：共6个，即URG、ACK、PSH、RST、SYN、FIN等。具体含义如下：
URG：紧急指针（urgent pointer）有效。
ACK：确认序号有效。
PSH：接收方应该尽快将这个报文交给应用层。
RST：重置连接。
SYN：发起一个新连接。
FIN：释放一个连接。
三次握手
﻿
四次挥手
﻿
HTTP协议超文本传输协议（英文：HyperText Transfer Protocol，缩写：HTTP）是一种用于分布式、协作式和超媒体信息系统的应用层协议。HTTP是万维网的数据通信的基础。
﻿
HTTP协议发展
﻿
HTTP请求与响应HTTP请求HTTP遵循请求（Request）/应答（Response）模型，Web浏览器向Web服务器发送请求时，Web服务器处理请求并返回适当的应答。
﻿
HTTP请求包括三部分，分别是请求行（请求方法）、请求头（消息报头）和请求正文。
﻿
﻿
﻿
HTTP请求头请求头只出现在HTTP请求中，请求报头允许客户端向服务端传递请求的附加信息和客户端自身信息。
Host 请求报头域主要用于指定被请求资源的Internet主机和端口。
User-Agent 请求报头域允许客户端将它的操作系统、浏览器和其他属性告诉服务器。
Referer 包含一个URL，代表当前访问URL的上一个URL，也就是说，用户是从什么地方来到本页面。当前请求的原始URL地址。
Cookie 是非常重要的请求头，常用来表示请求者的身份等。
Accept 这个消息头用于告诉服务器客户端愿意接受那些内容，比如图像类，办公文档格式等等。
HTTP请求方法HTTP1.0 定义了三种请求方法： GET, POST 和 HEAD方法。
HTTP1.1 新增了五种请求方法：OPTIONS、PUT、PATCH、DELETE、TRACE 和 CONNECT 方法。
﻿
﻿
HTTP响应HTTP响应报文也由三部分组成：响应行、响应头、响应体
﻿
﻿
HTTP响应头响应头是服务器根据请求向客户端发送的HTTP头。
﻿
状态码当浏览者访问一个网页时，浏览者的浏览器会向网页所在服务器发出请求。当浏览器接收并显示网页前，此网页所在的服务器会返回一个包含HTTP状态码的信息头（server header）用以响应浏览器的请求。
1xx消息——请求已被服务器接收，继续处理
2xx成功——请求已成功被服务器接收、理解、并接受
3xx重定向——需要后续操作才能完成这一请求
4xx请求错误——请求含有词法错误或者无法被执行
5xx服务器错误——服务器在处理某个正确请求时发生错误
常见的状态码描述如下：200：客户端请求成功，是最常见的状态。
302：重定向。
404：请求资源不存在，是最常见的状态。
400：客户端请求有语法错误，不能被服务器所理解。
401：请求未经授权。
403：服务器收到请求，但是拒绝提供服务。
500：服务器内部错误，是最常见的状态。
503：服务器当前不能处理客户端的请求。
非阻塞I/OSocket请求Socket实现服务器与客户端之间的物理连接，并进行数据传输。主要有TCP/UDP两个协议。Socket处于网络协议的传输层。
Socket数据处理流程
﻿
I/O IO (Input/Output，输入/输出)即数据的读取（接收）或写入（发送）操作，通常用户进程中的一个完整IO分为两阶段：用户进程空间<-->内核空间、内核空间<-->设备空间（磁盘、网络等）。IO有内存IO、网络IO和磁盘IO三种，通常我们说的IO指的是后两者。
阻塞I/O进程发起IO系统调用后，进程被阻塞，转到内核空间处理，整个IO处理完毕后返回进程。操作成功则进程获取到数据。阻塞式IO的特点就是在I/O执行的两个阶段都被阻塞了——阻塞等待数据，阻塞拷贝数据。
﻿
阻塞IO是socket的默认设置，其模型如下图所示.
﻿
非阻塞I/O进程发起IO系统调用后，如果内核缓冲区没有数据，需要到IO设备中读取，进程返回一个错误而不会被阻塞；进程发起IO系统调用后，如果内核缓冲区有数据，内核就会把数据返回进程。
﻿
具体模型如下图所示.
﻿
NIONIO主要有三大核心部分：Channel(通道)，Buffer(缓冲区),Selector。NIO基于Channel和Buffer(缓冲区)进行操作，数据总是从通道读取到缓冲区中，或者从缓冲区写入到通道中。
﻿
﻿
I/O复用IO复用(IO multiplexing)，也称事件驱动IO(event-driven IO)，就是在单个线程里同时监控多个套接字，通过 select 或 poll 轮询所负责的所有socket，当某个socket有数据到达了，就通知用户进程。目前支持I/O复用的系统调用有select、pselect、poll、epoll
﻿
IO复用常见的应用场景：
客户程序需要同时处理交互式的输入和服务器之间的网络连接。
客户端需要对多个网络连接作出反应。
服务器需要同时处理多个处于监听状态和多个连接状态的套接字
服务器需要处理多种网络协议的套接字。
﻿
﻿
select(poll)read过程
﻿
epoll的read过程
﻿
select阻塞过程
﻿
参考：
https://blog.csdn.net/qq_39521554/article/details/79894501
https://www.cnblogs.com/bj-mr-li/p/11106390.html
﻿