第八周总结

1. 数据结构与算法

数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。而程序就等于算法加数据结构。

1.1时间复杂度与空间复杂度

• 时间复杂度

(1) 并不是计算程序具体运行的时间，而是算法执行语句的次数（是估算）

(2) O(2^n)表示对n数据处理需要进行2^n次计算

(3) O(1), O(log(n)), O(n^a )多项式时间复杂度

(4) O(a^n)和O(n!)非多项式时间复杂度





• 空间复杂度

(1) 一个算法在运行过程中临时占用存储空间大小的量度

(2) O(n)表示需要临时存储n个数据

1.2 NP问题

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

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

NP ?= P（NP问题不一定是P问题，比如：数独）

NP-hard问题：比NP问题更难的问题( NP问题的解法可以规约到NP-hard问题的解法)

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

1.3 数组

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

数组的下标访问数据时间复杂度为O(1)。



1.4 链表

链表（LinkedList）也是一种线性表数据结构。链表通过指针将一组零散的内存块串联在一起。链表中每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。链表的查找复杂度是O(n)。

链表中增删数据要比数组性能好

1.5 数组+链表

数组读取快，增删慢，链表读取慢，增删快，可以用数组+链表实现快速查找和快速增删的数据结构。

1.6 Hash表

hash表是通过数组实现的，通过计算key值的hash code，来快速定位到数据的内存地址，时间复杂度是O(1)

如果不同的key，通过hash算法算出了相同的hash code，这个时候就存在hash冲突了，一般的方法是在hash表的数组中放一个链表，把冲突的数据加到链表的后面。如：jdk1.7中的HashMap就是基于数组+链表实现的，jdk1.8之后做了优化，当链表的长度过长（当链表长度大于8）会将链表转为红黑树，减少查询的开销。



1.7 栈

栈就是在线性表的基础上加了这样的操作限制条件：后面添加的数据，在删除的时候必须先删除，即通常所说的“后进先出”。

如：线程调用栈

1.8 队列

队列也是一种操作受限的线性表，栈是后进先出，而队列是先进先出。

如：阻塞等待的线程被放入队列

典型应用场景：生产者消费者

应用案例：

• 用队列搜索好友中关系最近的有钱人



• 用队列搜索最短路径



基本思路就是，从起点开始，把下一层关联的节点放入队列，然后依次取出处理，然后把这个节点的下一层节点也放入队列，以此来达到广度优先搜索。

1.9 树

树是非线性表结构，由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；



• 二叉排序树

左子树上所有的节点的值均小于或等于它的根节点的值。

右子树上的所有节点的值均大于或等于它的根节点的值。

左右子树也分别为二叉排序树。



• 不平衡的二叉排序树



• 平衡的二叉排序树

从任何一个节点出发，左右子树深度之差的绝对值不超过1。

左右子树仍然为平衡二叉树。



平衡二叉树在插入时，最多只需要两次旋转就会重新恢复平衡。

删除时，需要维护从删除节点到根节点这条路径上所有节点的平衡性，时间复杂度O(log n)





• 红黑（排序）树

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

根节点是黑色的

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

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

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



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

• 红黑（排序）树 VS 平衡二叉树

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

在大量删除的情况下，红黑树的效率高

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



• 跳表

跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。首先在最高级索引上查找最后一个小于当前查找元素的位置，然后再跳到次高级索引继续查找，直到跳到最底层为止

跳表跟红黑树&平衡二叉树一样都是提升查询效率的，不同的是跳表通过空间换时间，大大降低了实现的难度，目前在Redis和LeveIDB中都有用到。





1.10 常用算法

• 穷举算法

• 递归算法

如：快速排序

时间复杂度：n*log(n)

• 贪心算法

如：背包问题，小偷背了一个4磅背包去商城偷东西，将那些商品放入到背包才能利益最大化

改进贪心算法-迪特斯特拉（最快路径）

核心是找到起点到每个节点的最快路径



• 动态规划

• 遗传算法



2. 网络通信协议

2.1 网络通信协议

• OSI七层模型和TCP/IP四层模型





• 网络数据包格式



• 物理层

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



• 数据链路层

链路层就是将数据封装成帧，以帧为单位通过物理层进行通信，可以在帧上进行数据检验和流量控制。链路层会定义帧的大小，这个大小被称为最大传输单元。数据链路层会将封装好的帧添加一个帧头，帧头里记录的一个重要信息就是发送者和接收者的MAC地址。



• 网络层

网络层IP协议使得互联网应用根据IP地址访问到目标服务器，请求到运营商交换机，交换机根据IP进行路由转发，中间经过很多转发节点，最后到达目标服务器。网络层的数据需要交给数据链路层进行处理，而链路层的大小定义了最大传输单元，网络层的IP数据必须要小于最大传输单元才能进行网络传输，这个数据包也有一个IP头，主要包括的就是发送者和接收者的IP地址。



• 传输层

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

TCP协议是一种面向连接的、可靠的、基于字节流的传输层协议。



TCP建立连接三次握手与关闭连接四次挥手





• 应用层

包括HTTP、HTTPS、RPC等协议



HTTP请求的七种方法：GET、HEAD、POST、PUT、DELETE、TRACE、OPTIONS

HTTP响应的5种状态：

1xx（消息，请求已被服务器接收，继续处理）

2xx（成功，请求已被服务器接收、理解、并接受）

3xx（重定向，需要后续操作才能完成这一请求）

4xx（请求错误，请求含有词法错误或者无法被执行）

5xx（服务器错误，服务器在处理某个正确请求时发生错误）

HTTP协议版本：

HTTP/1.0：每次请求都需要创建连接&关闭连接

HTTP/1.1：连接keep-alive，一个连接可以顺序发送多个请求

HTTP/2：多路复用

2.2 非阻塞网络I/O



2.3 数据库架构原理与性能优化