数据结构与算法

算法中几个概念：

1、时间复杂度

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

常见时间复杂度

• 常数阶 O(1),

• 对数阶 O(log2 n),

• 线性阶 O(n),

• 线性对数阶 O(n log2 n),

• 平方阶 O(n^2)，

• 立方阶 O(n^3)

• k 次方阶 O(n^K),

• 指数阶 O(2^n)。

常用的时间复杂度所耗费的时间从小到大依次是：

　　O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

计算方法 

①选取相对增长最高的项 

②最高项系数是都化为 1 

③若是常数的话用 O（1）表示 

如 f（n）=2*n^3+2n+100 则 O（n）=n^3。

2、空间复杂度

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

计算方法： 

①忽略常数，用 O(1)表示 

②递归算法的空间复杂度=递归深度 N*每次递归所要的辅助空间 

③对于单线程来说，递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数，因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。

常见排序算法的时间与空间复杂度

3、NP 问题

P：存在多项式时间算法的问题，能在多项式时间复杂度内解决。

NP：能在多项式时间内验证得出一个正确解的问题。

P 问题是 NP 问题的子集，因为存在多项式时间解法的问题，总能在多项式时间内验证它。

NP-hard：比 NP 更难于解决的问题。

NPC：是一个 NP-hard 问题，也是一个 NP 问题。存在这样一个 NP 问题，所有的 NP 问题都可以约化成它。

常见数据结构

1、线性表

数组：内存中一块连续的空间，存放相同数据类型，随机快速读写，时间复杂度 Q(1)

链表：可用零散内存空间存储，每个元素必包含指向下一元素的内存地址指针，查找元素只能遍历元素，时间复杂度 Q（N）

Hash 表：散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。

2、栈与队列

栈和队列也是比较常见的数据结构，是比较特殊的线性表。

栈：栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫作栈顶，对栈的基本操作有 push(进栈)和 pop(出栈)，前者相当于插入，后者相当于删除最后一个元素。栈有时又叫作 LIFO(Last In First Out)表，即后进先出。

队列：特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

典型应用：生产者消费者。

问题：用队列搜索好友中关系最近的有钱人。用队列搜索最短路径。

3、树

树型结构是一类非常重要的非线性数据结构，其中以树和二叉树最为常用。

树：树 是由 n（n>=1）个有限节点组成一个具有层次关系的集合。

二叉（排序）树：每个节点最多有两棵子树的树结构。通常子树被称作“左子树”和“右子树”。（排序）左子树上所有节点的值均小于或等于它的根节点值；右子树上所有节点的值均大于或等于它的根节点值。

平衡二叉（排序）树：AVL 树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过 1

旋转二叉树恢复平衡

红黑（排序）树：节点只有两种颜色：红色和黑色；根节点是黑色的。每个叶子节点（NIL）都是黑色。从跟到叶子节点，不会出现两个连续红色节点。从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。

4、跳表

跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它，它的效率和红黑树以及 AVL 树不相上下，但跳表的原理相当简单，只要你能熟练操作链表，就能轻松实现一个 SkipList

查找：

插入

常用算法

递归算法

原理：一种通过重复将问题分解为同类的子问题而解决问题的方法

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

贪心算法

原理：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

背包问题：有一个贼在偷窃一家商店时，发现有 n 件物品，第 i 件物品价值 vi 元，重 wi 磅，此处 vi 与 wi 都是整数。他希望带走的东西越值钱越好，但他的背包中至多只能装下 W 磅的东西，W 为一整数。应该带走哪几样东西？

改进贪心算法-迪杰斯特拉算法

从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

动态规划算法

将一个问题分解为若干个子问题，对每个子问题求最优解，前一个子问题的最优解，为下面的子问题提供了有效信息，依次解决子问题，最后一个子问题就是初始问题的最优解。

遗传算法

关键步骤：

（1）基因编码：在这个过程中，尝试对一些个体的基因做一个描述，构造这些基因的结构，有点像确定函数自变量的过程。 

（2）设计初始群体：在这里需要造一个种群出来，这些种群有很多生物个体但基因不同。 

（3）适应度计算（剪枝）：这里对那些不符合要求的后代进行剔除，不让他们产生后代。否则他们产生的后代只会让计算量更大而对逼近目标没有增益。 

（4）产生下一代：有 3 种方法，即：直接选择，基因重组，基因突变 。

应用领域：如 TSP 问题（旅行商问题），九宫问题，生产调度问题，背包问题等。

假设有一个背包，可以放置 80 公斤的物品：

基因编码：一共有 6 种物品，每种物品的有无可以作为一个独立的基因片段。

基因组合：染色体

设计初始染色体：随机（人为或算法选择）

适应函数与控制参数：总价值、总重量

产生下一代：染色体交叉遗传

循环迭代：连续几代的适应函数最大值不再增加，出现这种情况则判断为收敛。

网络通信协议

WEB 请求的通信历程

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

网路数据包格式

TCP 三次握手和四次挥手

建立连接，三次握手

• 第一次：客户端发送初始序号 x 和 syn=1 请求标志

• 第二次：服务器发送请求标志 syn，发送确认标志 ACK，发送自己的序号 seq=y，发送客户端的确认序号 ack=x+1

• 第三次：客户端发送 ACK 确认号，发送自己的序号 seq=x+1，发送对方的确认号 ack=y+1

关闭连接，四层挥手

• 第一次挥手：客户端发出释放 FIN=1，自己序列号 seq=u，进入 FIN-WAIT-1 状态

• 第二次挥手：服务器收到客户端的后，发出 ACK=1 确认标志和客户端的确认号 ack=u+1，自己的序列号 seq=v，进入 CLOSE-WAIT 状态

• 第三次挥手：客户端收到服务器确认结果后，进入 FIN-WAIT-2 状态。此时服务器发送释放 FIN=1 信号，确认标志 ACK=1，确认序号 ack=u+1，自己序号 seq=w，服务器进入 LAST-ACK（最后确认态）

• 第四次挥手：客户端收到回复后，发送确认 ACK=1，ack=w+1，自己的 seq=u+1，客户端进入 TIME-WAIT（时间等待）。客户端经过 2 个最长报文段寿命后，客户端 CLOSE；服务器收到确认后，立刻进入 CLOSE 状态。

HTTP 请求的 7 种方法

1 GET，发送请求来获得服务器上的资源，请求体中不会包含请求数据，请求数据放在协议头中。

2 POST，向服务器提交资源让服务器处理，比如提交表单、上传文件等。

3 HEAD，和 get 一样，但是响应中没有呈现数据，而是 http 的头信息，主要用来检查资源或超链接的有效性或是否可以可达、检查网页是否被串改或更新，获取头信息等，特别适用在有限的速度和带宽下。

4 PUT，和 post 类似，html 表单不支持，发送资源与服务器，并存储在服务器指定位置，要求客户端事先知

道该位置；比如 post 是在一个集合上（/province），而 put 是具体某一个资源上（/province/123）。所以 put 是安全的，无论请求多少次，都是在 123 上更改，而 post 可能请求几次创建了几次资源。

5 DELETE，请求服务器删除某资源。和 put 都具有破坏性，可能被防火墙拦截。如果是 https 协议，则无需担心。

6 OPTIONS，获取 http 服务器支持的 http 请求方法，允许客户端查看服务器的性能，比如 ajax 跨域时的预检等。

7 TRACE，回显服务器收到的请求，主要用于测试或诊断。一般禁用，防止被恶意攻击或盗取信息。

HTTP 请求响应的 5 种状态

1XX-信息性状态码（Informational）-服务器正在处理请求

2XX-成功状态码（Success）-请求已正常处理完毕

3XX-重定向状态码（Redirection）-需要进行额外操作以完成请求

4XX-客户端错误状态码（Client Error）-客户端原因导致服务器无法处理请求

5XX-服务器错误状态码（Server Error）-服务器原因导致处理请求出错

HTTP 协议各版本

HTTP/0.9

HTTP 协议的最初版本，功能简陋，仅支持请求方式 GET，并且仅能请求访问 HTML 格式的资源。

HTTP/1.0

在 0.9 版本上做了进步，增加了请求方式 POST 和 HEAD；不再局限于 0.9 版本的 HTML 格式，根据 Content-Type 可以支持多种数据格式，即 MIME 多用途互联网邮件扩展，例如 text/html、image/jpeg 等；同时也开始支持 cache，就是当客户端在规定时间内访问统一网站，直接访问 cache 即可。

但是 1.0 版本的工作方式是每次 TCP 连接只能发送一个请求，当服务器响应后就会关闭这次连接，下一个请求需要再次建立 TCP 连接，就是不支持 keepalive。

HTTP/1.1

解决了 1.0 版本的 keepalive 问题，1.1 版本加入了持久连接，一个 TCP 连接可以允许多个 HTTP 请求； 加入了管道机制，一个 TCP 连接同时允许多个请求同时发送，增加了并发性；新增了请求方式 PUT、PATCH、DELETE 等。

但是还存在一些问题，服务端是按队列顺序处理请求的，假如一个请求处理时间很长，则会导致后边的请求无法处理，这样就造成了队头阻塞的问题；同时 HTTP 是无状态的连接，因此每次请求都需要添加重复的字段，降低了带宽的利用率。

HTTP/2.0

为了解决 1.1 版本利用率不高的问题，提出了 HTTP/2.0 版本。增加双工模式，即不仅客户端能够同时发送多个请求，服务端也能同时处理多个请求，解决了队头堵塞的问题；HTTP 请求和响应中，状态行和请求/响应头都是些信息字段，并没有真正的数据，因此在 2.0 版本中将所有的信息字段建立一张表，为表中的每个字段建立索引，客户端和服务端共同使用这个表，他们之间就以索引号来表示信息字段，这样就避免了 1.0 旧版本的重复繁琐的字段，并以压缩的方式传输，提高利用率。

另外也增加服务器推送的功能，即不经请求服务端主动向客户端发送数据。

非阻塞网络 I/O

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