week 8 总结
时间复杂度
并不是计算程序具体运行的时间，而是算法执行语句的次数。O(1)，O(logn), O(n^a)属于多项式时间复杂度。O(a^n)和O(n!)属于非多项式时间复杂度。
空间复杂度
一个算法在运行过程中临时占用存储空间大小的度量。O(n)表示需要临时占用n个数据。
NP问题
P问题：能在多项式时间复杂度内解决的问题
NP问题：能在多项式时间复杂度内验证答案正确与否的问题。（典型：我可以在多项式时间复杂度内判断一个数字排列是否符合数独，但是却没办法在多项式时间复杂度内求解数独）
NP-hard问题：比NP问题更难的问题（NP问题的解法可以规约到NP-hard问题的解法）
NP完全问题：是一个NP-hard问题，也是一个NP问题
数据结构
数组
连续空间
数组中存放相同数据类型
以上两点保证了O1复杂度内快速定位到数据内存地址
链表
链表可以使用零散的内存空间存储数据。所以链表中每个数据元素都必须包含一个指向下一个数据元素的内存地址。
Hash表
既要求快速访问数据，又希望快速增删数据
栈
数组和链表都被称为线性表。栈就是在线性表的基础上加了这样的操作限制条件：后进先出。
队列
队列也是一种操作受限的线性表，栈是后进先出，而队列的先进先出。
树
一个结点可能有多个后继，最多一个前驱。二叉排序树是一种典型的树。左子树的所有结点均小于或等于根节点的值，右子树所有结点的值均大于或等于根节点的值。二叉树的时间复杂度一定是O(longn)吗？其实未必，如果是不平衡的，可能退化成O(n)。但是平衡二叉排序树的复杂度均为O(n)。对于平衡二叉树，从任何一个节点出发，左右子树深度之差的绝对值不超过1，并且左右子树仍然为平衡二叉树。不平衡的二叉树通过旋转来恢复平衡。插入时，最多只需要两次旋转就可以恢复平衡。删除时，需要维护从被删节点到根节点这条路径上所有节点的平衡性，时间复杂度是O(logn)。
红黑树
1）每个结点要么是黑色，要么是红色。
2）根节点是黑色。
3）叶子节点（NIL）是黑色。
4）从根节点到叶子节点，不会出现连续的红色节点。
5）从任何一个节点出发，到叶子节点，这条路径上都有相同数目 黑色节点。
红黑树是在排序二叉树的前提下附加了以上的约束条件，使得排序二叉树达到近似平衡的目的。
红黑树VS平衡二叉树
红黑树最多只需要3次旋转就会重新达成红黑平衡，时间复杂度是O(1)。在大量增删的情况下，红黑树的效率更高。但是，红黑树的平衡性不如平衡二叉树，查找效率差一点点。
Dijkstra算法
找出“最便宜”的节点，即可在最短时间内到达的节点。
更新该阶段的邻居的开销，检查是否有前往它们的更短路径，如果有，就更新开销。
重复这个过程，直到对图中的每个节点都这样做了。
计算最终路径。
动态规划
通过找到合适的角度，将所求解的目标值在某（几）个维度上展开，将一个大问题拆解为若干个小问题，从小问题的最优解，寻找大问题的最优解。
遗传算法
遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化工程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；产生编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。遗传算法得到的不一定是最优解：
Web请求一次网络通信的历程
OSI七层模型和TCP/IP四层模型
网络数据包格式
物理层
物理层负责数据的物理传输，计算机输入输出的只能是0，1这样的二进制数据，但是在真正通信的线路里面有光纤，电缆，无线等各种设备。光信号和电信号，以及无线电磁信号在物理上是完全不同的，如何让这些不同的设备能够理解，处理相同的二进制数据，这就是物理层要解决的问题。
链路层
链路层就是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流量控制等。链路层会定义帧的大小，称为最大传输单元（MTU）。数据链路层会将封装好的帧添加一个帧头，帧头记录的一个重要信息就是发送者和接受者的MAC地址。
网络层
网络层IP协议使得互联网应用根据IP地址就能访问到目标服务器，请求离开APP后，到达运营商的交换机，交换机会根据这个IP地址进行路由转发，可能中间会经过很多个转发节点，最后数据到达目标服务器。网络层的数据需要交给链路层进行处理，而链路层帧的大小定义了最大传输单元，网络层的IP数据必须要小于最大传输单元才能进行网络传输。
传输层协议
IP协议部署一个可靠的通信协议，不会建立稳定的通信链路，并不会确保数据一定送达。要保证通信的稳定可靠，需要传输层协议TCP。TCP协议是一种面向连接的，可靠的，基于字节流的传输层协议。TCP作为一个比较基础的通信协议，有很多重要的机制保证了TCP协议的可靠性和健壮性。比如：使用序列号进行TCP报文段的排序和判重；使用校验进行报文段的错误检测；使用确认和重传定时器进行丢包重传；流量控制，避免发送方发送数据过快而接收方接受不过来；拥塞控制，避免网络拥塞。
HTTP请求的7种方法
Get：只读请求，请求处理过程中不应该产生副作用，即web应用不应该因为get请求而发生任何状态改变。
Head：和get方法一样，但是只返回响应头。
Post：提交请求。
Put：上传请求。
Delete：删除URL标识的资源。
Trace：回显服务器收到的请求，用于测试或者诊断。
Options：请求服务器返回支持的所有HTTP请求方法，用于测试服务器是否正常。
HTTP协议版本
1.0：1996年发布，客户端和服务器之间交换的每个请求/响应都会创建一个新的TCP连接，会产生延迟。
1.1：加入了保持连接的概念来解决这个问题，降低了很多建立连接的开销。但是这个连接不能并发处理多个请求。
2.0：引入了HTTP流的概念，允许将多个不同的HTTP并发地复用同一个TCP连接，使得浏览器更高效地复用TCP连接。但是，TCP并不理解HTTP流，当多个HTTP请求复用一个TCP连接，如果前面的请求/响应没有处理完，后面的请求/响应也无法处理，也就是会出现队头阻塞的现象。
3.0：使用QUIC的传输协议。协议在传输层把流当作一等公民来看待。多个QUIC流共享相同的QUIC连接，因此不需要额外的握手和慢启动来创建新的QUIC流。QUIC流是独立的，其中一个流的丢包不会影响其他流。
BIO Blocking I/O阻塞I/O
进行I/O操作时，用户线程会一直阻塞，直到读操作或者写操作完成。
Socket接收数据，操作系统内核处理过程
非阻塞I/O（Non-Blocking I/O）
I/O操作立即返回，发起线程不会阻塞等待。
非阻塞read：
1）Socket接收缓冲区有数据，读n个（不保证数据被读完整，因此可能要读多次）
2）Socket接收缓冲区没数据，则返回失败（不会等待）
非阻塞write
1）Socket发送缓冲区满，返回失败（不会等待）
2）Socket发送缓冲区不满，写n个数据（不保证一次性全部写入，因此可能要多次写）
Select（poll）管理下的read过程
主要是通过遍历所有socket的方式。缺点是socket数量多时，遍历成本很高，拷贝成本也高。
epoll管理下的read过程
数据库架构
连接器：数据库连接器会为每个连接请求分配一块专用的内存空间用于会话上下文管理。建立连接对于数据库而言相对比较重，需要花费一定的时间。
语义分析与优化器：将各种复杂嵌套的SQL进行语义等价转换，得到有限几种关系代数计算结构，并利用索引等信息进一步进行优化。
为什么PrepareStatement更好
PrepareStatement会预先提交带占位符的SQL到数据库进行预处理，提前生成好执行计划，当给定占位符参数，真正执行SQL的时候，执行引擎可以直接执行，效率更好。另外，PrepareStatement可以防SQL注入。
数据库事务日志
进行事务操作时，事务日志文件会记录更新前 数据记录，然后再更新数据库中的记录，如果全部记录都更新成功，那么事务正常结束，如果过程中某条记录更新失败，那么整个事务全部回滚，以及更新的记录根据事务日志中记录的数据进行恢复，这样全部数据都恢复到事务提交前的状态，仍然保持数据一致性。
LSN：一个按时间顺序分配的唯一事务记录日志序列号。
TransID：产生操作的事务ID。
PageID：被修改的数据再磁盘上的位置。
PrevLSN：同一个事务产生的上一条日志记录的指针。
UNDO：取消本次操作的方法，按照此方法回滚。
REDO：重复本次操作的方法。
还未添加个人签名 2018.03.25 加入
还未添加个人简介
评论