第八周课程总结

用户头像
考尔菲德
关注
发布于: 2020 年 07 月 29 日

一、数据结构与算法

1、时间复杂度和空间复杂度

2、NP问题

P问题

NP问题

NP ?= P (NP问题是不是就是P问题)

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

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



二、线性表数据结构

1、数组

结构:

  • 内存中一块连续的空间

  • 数据类型相同

特征:

  • 随机快速读写,根据数组的下标访问数据,时间复杂度为O(1)

2、链表

结构:

  • 零散的内存空间存储数据

  • 每个数据元素包含一个指向下一个数据元素的内存地址指针;

特性:

  • 遍历链表来查找数据,时间复杂度是O(N)



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

数组随机读取元素的性能好很多



数组链表结合,实现快速查找和快速增删,结构类似于Hash表



3、Hash表

既能快速访问数据,又能快速增删数据

Hash冲突

4、栈

数组和链表都是线性表

在线性表的基础上加上这样的操作限制:后进先出,则为栈

线程运行时专有内存即为线程栈

5、队列

队列也是一种操作受限的线性表,先进先出!

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



用队列搜索好友中关系最近的有钱人,如何实现?

对队列搜索最短路径

三、树

1、二叉树

1.1二叉排序树

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

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

二叉排序树的查找的时间复杂度是 o(log2N)

不平衡的二叉排序树,如下



已经退化为一个链表了



1.2平衡二叉排序树

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

每个左右子树自己任然为平衡二叉排序树



旋转二叉树 最多只需要两次旋转就会重新恢复平衡

删除时,需要维护从被删除节点到根节点这条路径上所有节点的平衡性,时间复杂度为O(logN);



2、红黑(排序)树

概念:

    每个节点只有两种颜色:

    根节点是黑色的

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

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

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

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

在大量增删的情况下,红黑树的效率更高

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

TreeMap就是使用红黑树实现;



3、跳表

跳表的数据结构如下:





提升链表查询性能

但是空间复杂度比较高



四、常用的算法

1、穷举算法

2、递归算法

时间复杂度 n* log(n)



3、贪心算法

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

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

算法描述:

1、找出”最便宜“的节点,即可在最短时间内到达的节点

2、更新该节点的邻居的开销,检查是否有前往他们的更短路径,如果有,就更新其开销

3、重复这个逻辑,知道对图中的每个节点都这样做

4、计算最短路径



4、动态规划

动态规划算法解决背包问题

通过找到合适的角度,将所求解的目标值在某(几)个维度上展开,将一个大问题拆解为若干个小问题,从小问题的最优解,寻找大问题的最优解



5、遗传算法解决背包问题

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法

五、网络通信协议

Web请求的一次网络通信历程

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

网络数据包格式

1、物理层

负责数据的物流传输

通信线路有光纤、电缆、无线和无线电磁信号等;

如何让这些不同的设备能够理解和处理相同的二进制数据,这是物理层要解决的问题

2、链路层

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

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



链路层实现负责均衡

IP负载均衡

3、传输层

TCP建立连接的三次握手过程:

TCP关闭连接4次挥手

4、应用层HTTP协议

HTTP请求的7种方法

Get

Head

Post

Put

Delete

Trace

Options



HTTP响应的5种状态

1xx消息

2xx成功

3xx重定向

4xx请求错误

5xx服务器错误



HTTP/1.0 — 客户端和服务器之间交换的每个请求/响应都会创建一个新的TCP连接,这意味着所有请求之前都需要进行TCP握手连接,因此所有请求都会产生延迟



HTTP/1.1 — 允许客户端复用TCP连接,从而分摊了简历初始连接和针对多个请求缓慢启动的成本,但任意时点上每个连接只能执行一次请求/响应交换



HTTP/2 —  HTTP流的概念,允许将不同的HTTP并发地复用到同一个TCP连接上,使浏览器更高效地复用TCP连接。但是会出现队头阻塞想象



HTTP/3 —  使用QUIC(一种新的互联网传输协议),数据包封装在UDP数据包内;



5、非阻塞网络I/O

计算机之间如何进行网络请求

操作系统提供了编程接口 Socket



6、BIO Blocking I/O 

阻塞I/O:进行I/O操作时,用户线程一直阻塞,直到读操作或者写操作完成

Socket接受数据,系统内核的处理过程

非阻塞I/O

Java NIO(New I/O) 



系统I/O复用方式:select/poll/epoll

六、数据库架构原理

1、数据库架构



1)连接器

连接器会为每个连接请求分配一块专用的内存空间用于会话上下文管理,简历连接对于数据库而言相对比较重,需要花费一定的时间,因此应用程序启动的时候,通常会初始化建立一些数据库连接放在连接池里,这样当处理外部请求执行SQL操作的时候,就不需要花费时间建立连接了。

2)语法分析器
3)语义分析与优化器

语义分析与优化就是将各种复杂嵌套的SQL进行语义等价转化,得到有限几种关系代数计算结构,并利用索引等信息进一步进行优化

4)执行计划 explain

Key:索引类型,NULL表示没有索引

Rows: 需要处理的行数

Possible_keys: 潜在可以利用的索引

2、索引

1)B+树结构的理解



2)聚簇索引

聚簇索引:数据库记录和索引存储在一起,MySql数据库的主键就是聚簇索引,主键ID和所在的记录行存储在一个B+树中;

3)非聚簇索引

非聚簇索引在叶子节点记路的就不是数据行记录,而是聚簇索引,也就是主键,通过非聚簇索引找到主键索引,再通过主键索引找到行记录的过程也称作回表;

4)添加必要的索引优化SQL查询性能

5)合理使用索引

  • 添加索引的alter操作会消耗较长的时间

  • Alter操作期间,所有数据库的增删改操作全部阻塞,对应用而言,因为连接不能释放,事实上,查询也被阻塞

  • 删除不用的索引,避免不必要的增删开销

  • 使用更小的额数据类型创建索引

3、数据库事务

事务特性ACID

  • 原子性

  • 隔离性

  • 持久性

  • 一致性

数据库通过事务日志来实现事务



用户头像

考尔菲德

关注

还未添加个人签名 2018.04.19 加入

还未添加个人简介

评论

发布
暂无评论
第八周课程总结