数据结构与算法

一、时间复杂度

我的理解：表示算法运行得到想要的解所需的计算工作量，他探讨的是当输入值接近无穷时，算法所需工作量的变化快慢程度。



举个例子

int cal(int n) {
 int sum = 0; //常量级执行时间
 int i = 1;  //常量级执行时间
 int j = 1; //常量级执行时间
 for (; i <= n; ++i) { 
     j = 1; 
     for (;j <= n; ++j) { 
       sum = sum + i * j ;
     }
   }
 }

设每行代码的执行时间为x

2、3、4行的时间即3x

5、6行执行了n遍，所以是2nx

7、8行执行了n*n遍, 所以是n*n*x

整体时间T(n) = (3+2n+2n^2) *x 的时间



可以看出所有代码的执行时间与每行代码的执行次数n成正比。



T(n)表示代码的执行时间，n表示数据规模的大小；f(n)表示每行代码执行的次数总和。

上述公示中的O表示了代码的执行时间T(n)与f(n)表达式成正比。

当n趋向于无穷大时，公示中的低阶，常量，系数三部分并不左右增长趋势，所以它们都可以忽略，只需要记录一个最大量级就可以了。



拿上面的例子来进行分析，2、3、4行都是常量级执行时间，它和n的规模没有关系。假设当n趋向于无穷大的时候，2、3、4行的代码完全可以忽略不计，而大 O 这种复杂度表示方法只是表示一种变化趋势，是估算，所以上述例子的时间复杂度就可以记为 O(n^2)。



1.并不是计算程序具体运行的时间，而是算法执行语句的次数，大O时间复杂度表示法表示的仅是一种变化趋势，当程序所处理的问题规模扩大后，程序需要的时间长度对应增长得有多快。

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

3.O(1)、O(log(n))、O(n^a)多项式时间复杂度 [n是数据的执行次数，a是常量]

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





二、空间复杂度

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

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



三、NP问题

多项式时间

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当程序所处理的问题规模扩大后，程序需要的时间长度对应增长得有多快。也就是说，对于某一个程序，其处理某一个特定数据的效率不能衡量该程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。

不管数据有多大，程序处理所花的时间始终是那么多的，我们就说这个程序很好，具有O(1)O(1)O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，比如找n个数中的最大值这个程序的时间复杂度就是O(n)O(n)O(n)，为线性级复杂度，而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，时间复杂度是O(n2)O(n^2)O(n2)，为平方级复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(an)O(a^n)O(an)的指数级复杂度，甚至O(n!)O(n!)O(n!)的阶乘级复杂度。不会存在 O(2∗n2)O(2*n^2)O(2∗n2) 的复杂度，因为前面的那个"2"是系数，根本不会影响到整个程序的时间增长。同样地，O(n3+n2)O(n^3+n^2)O(n3+n2) 的复杂度也就是O(n3)O(n^3)O(n3)的复杂度。因此，我们会说，一个O(0.01∗n3)O(0.01*n^3)O(0.01∗n3)的程序的效率比O(100∗n2)O(100*n^2)O(100∗n2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n3)O(n^3)O(n3)的复杂度将远远超过O(n2)O(n^2)O(n2)。我们也说，O(n100)O(n^{100})O(n100)的复杂度小O(1.01n)O(1.01^n)O(1.01n)的复杂度。

容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者。像O(1)O(1)O(1),O(ln(n))O(\ln(n))O(ln(n)),O(na)O(n^a)O(na)等，我们把它叫做多项式级复杂度，因为它的规模n出现在底数的位置；另一种像是O(an)O(a^n)O(an)和O(n!)O(n!)O(n!)等，它是非多项式级的复杂度，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。

P问题

能在多项式时间复杂度内解决的问题，就是在常规时间内能够解决的问题。

NP问题

能在多项式时间复杂度内验证答案正确与否的问题，提出一个假设，能在常规时间内验证这个问题是否正确。

NP-hard问题

比NP问题更难的问题(NP问题的解法可以规约到NP-hard问题)，解决了一个NP-hard问题，也就解决了一类NP问题。

NP完全问题

是一个NP-hard问题，也是一个NP问题





数独，这是一个NP问题，不是一个P问题。因为我们无法在多项式的时间内把这些数字都填正确了。

算法儿只能是暴力拆解，穷举的方式来计算，这个显然不是一个P问题。

但这个数独的某个答案是可以在多项式时间内可以验证的，所以它是一个NP问题。

四、数组

特性：1.内存中一块儿连续的空间

2.数组中必须存放相同的数据类型

随机快速读写是数组的一个重要的特性，根据数组的下标来访问数据，时间复杂度为O(1)



五、链表



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



六、哈希表



这种数据结构哈希表的本质就是一个数组，它的逻辑是根据key来计算一个Hash值，简单的做法是对数组的长度取摩，取得余数，上面的例子就可以把内容写入到数组下标为5的位置。在增删数据、访问数据的时候它的时间负载度也是O(1)。



对于哈希冲突问题，例如上面的多个数字对8去摩尔的时候余数都是5，这个时候就要使用数组加链表儿的形式了。

七、栈



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



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



线程运行时专有内存为什么被称为线程栈

void f(){
  int x = g(1);
  x++;//g函数返回，当前
  //堆栈顶部为f函数栈帧，当当前栈帧继续执行f函数的代码.
}
ing g(int x) {
  return x +1;
}





如上所示，f和g函数的局部变量都放到栈里。栈的特征是后进先出的。



八、堆

堆是所有线程共享的



九、队列



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

典型的应用场景：生产者消费者；阻塞等待的线程被放入队列。



十、树

二叉排序树

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

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

左、右子树也分别为二叉排序树，平衡的二叉排序树它的时间复杂度是O(logN)





不平衡的二叉排序树



这个不平衡的二叉排序树，上图要是不算12了，就退化成一个链表儿了，时间复杂度也就变成了O(n)了



旋转二叉树恢复平衡

插入时，最多只需要两次旋转就会重新恢复平衡。删除时，需要维护从被删节点到根节点这条路径上所有节点的平衡性，时间复杂度O(logN)





红黑(排序)树

每个节点自由两种颜色：红色和黑色。

根节点是黑色的。

每个叶子节点(NIL)都是黑色的空节点。

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

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



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

在大量增删的情况下，红黑树的效率更高，红黑树的平衡性不如平衡二叉树，查找效率要查一些。



跳表



把当前的元素排列成一个链表儿，然后隔着几个组成新的链表儿，然后去遍历小的链表。这种算法逻辑是用空间换时间。



十一、常用算法

1.穷举算法

此中算法只是把所有的可能性都列举出来，然后进行处理。它只能适用于小的数据，大一点儿规模的数据就不行了，比如1000的阶乘，这个数字就很大了。

2.递归算法

有一个出口，然后自己调用自己。

3.贪心算法

定义：每一步都找一个当前的最优解，注意当前的最优解不见得是整体的最优解，它只能近似得得到一个较优解。

举个例子:

背包问题：小偷背了一个4磅的背包去商城偷东西，将哪些商品放入背包才能收益最大化。



用贪心算法来算的话，就看这些商品里面哪个是最值钱的，把最值钱的放进去，按照这个思路就是把音响放进去够了4磅就走了

改进贪心算法-迪杰斯特拉算法(最快路径)



算法核心：找到起点到每个节点的最快路径





我的理解及描述：

定义两个集合，

1.最短路径计算完成的节点集S 和 未计算完成的节点集T

2.每次将从T中挑选V0->Vt(最小的节点) Vt加入S，并更新V0经由Vt到T中剩余节点的更短距离shortest，直到T中的节点全部加入S中。



注：S为已求出最短路径的节点集合，T为未求出最短路径的节点集合。



源节点只允许将S中的节点作为中间节点来计算到达其它节点的最短路径，随着S中节点的增加，源节点可达的节点才会增加。



1) 将源节点(即节点V0)加入s中 此时 S { V0 } T { V1, V2, V3,V4,V5,V6 }

2) S中现有V0，源节点V0可达T中的V1和V2，V0-V1距离为4，V0-V2距离为11，按从小到大排序，因此选择v1加入到S中，然后更新节点V1作为中间节点可以到达其它节点的距离，此时

S {V0, V1 } T{V2,V3,V4,V5,V6}

3) S中现有节点V0和V1，源节点V0可达T中的节点为V2和V4.

V0--> V1 -->V4 4+21 = 25

V0--> V2 路径值为 11 ，因此V2移如S

S {V0, V1, V2 } T{V3,V4,V5,V6}

4) 根据S现有节点，目前可达T中的V3、V4和V5

V0->V1->V4 4+21 = 25

V0->V2->V3 11+5=16 这条路最小一次V3入选

V0->V2->V5 11+8=19

S {V0, V1, V2,V3 } T{V4,V5,V6}

5) 根据S现有节点，目前可达T中的V4和V5

V0->V1->V4 4+21=25

V0->V2->V3->V4 11+5+5=21

V->V2->V5 11+8=19 因此V5入选

S {V0, V1, V2,V3,V5 } T{V4,V6}

6) 根据S现有节点，目前可达T中的V4

V0->V1->V4 4+21=25

V0->V2->V3->V4 11+5+5=21 因此V4入选

V0->V2->V5->V4 11+8+12=31

S {V0, V1, V2,V3,V5,V4 } T{V6}

7) 根据S现有节点，目前已可达T中的V6，计算路径

V0->V1->V4->V6 4+21+4=29

V0->V2->V3->V4->V6 11+5+5+4 = 25 这条路径最省时

V0->V2->V5->V4->V6 11+8+12+4 = 35



S {V0, V1, V2,V3,V5,V4,V6 } T{}



5.动态规划

定义：把一个复杂问题分解成若干个子问题，并且寻找最优子问题的一种思想，而不是一种特定的算法。

还是使用上面的背包问题用动态规划的思想来解决



用二维表把1-4磅的所有可能性都列到表格中，上图右上音响是4磅所以1磅的是放不下的因此就还还是把吉他装进去，也就是过往的最优解，其它的以此类推。可以得到上图右下的 3500元的也就是最值钱的，也就是最优解。



十二、网路



会话层是用于通话保持的,表示层是数据格式





主机A要想和主机B协议，主机A上层是依赖于下层的，每次往下走的时候都会打响应的包，到了主机B的网络后再层层拆包最后得到了想要的数据



网络数据包的格式



最后在物理链路上传输的就是最外面的携带链路层协议头的数据包

物理层

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



链路层

是将数据进行封装后交给物理层进行传输，主要就是将数据封装成数据帧，以帧为单位通过物理层进行通信，有了帧，就可以在帧上进行数据校验，进行流量控制。

链路层会定义帧的大小，这个大小也被成为最大传输单元。像HTTP要在传输的数据上添加一个HTTP头一样，数据链路层也会将封装好的帧添加一饿帧头，帧头里记录的一个重要信息就是发送者和接受者的MAC地址。MAC地址是网卡的设备标识符，是唯一的，数据帧通过这个信息确保数据送达到正确的目标机器。



传输层

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

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

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

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

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

控制流量，避免主机分组发送的过块而使接收方来不及完全收下

拥塞控制，发送放根据网络承载情况控制分组的发送量，以获得高性能能同时避免拥塞崩溃丢失包的重传

TCP连接的三次握手



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.



计算机值钱如何进行网络请求？



操作系统是通过网络通信的编程接口的，也就是Socket，下图是最基础的通信流程



1.操作系统去New一个Socket，然后绑定一个端口，操作系统就会去监听这个端口儿了，也就是程序持续运行的一个Socket

2.当第一个请求抵达服务器的时候，客户端和服务器建立起来了另一个Socket



多线程服务器-客户端的模式



1.服务启动的时候建立了单独的socket

2.每个请求上了时候建立单独的线程去处理





TomCat的处理方式，采用线程池的形式



系统内核的处理过程



十三、数据库架构



聚簇索引

它的数据库击落和索引存储在一起。

MySQL数据库的主键就是聚簇索引，主键ID和所在的记录行存储在一个B+树中



非聚簇索引

在叶子节点记录的就不是数据行记录，而是聚簇索引，也就是主键。

通过非聚簇索引找到主键索引，再通过主键索引找到行记录的过程也被乘坐回表。