数据结构与算法以及网络与数据库总结

用户头像
小叶
关注
发布于: 2020 年 07 月 29 日

数据结构与算法

时间复杂度与空间复杂度

概述:

时间复杂度是描述程序运行时间的一个维度,空间复杂度是描述程序运行期间消耗的内存的一个维度。

时间复杂度:

  • 不是计算程序具体运行的时间,而是算法执行语句的次数

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

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

  • 非多项式时间复杂度:O(a^n),O(n!)

空间复杂度:

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

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

NP问题:

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

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

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

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

数据结构

数组

  • 创建数组必须要内存中一块连续的内存空间。

  • 数组的数据类型必须一致(不一致会导致不能根据偏移快速寻址)

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

链表

  • 可以使用零散内存空间存储数据

  • 所有链表中每个数据都必须包含一个指向下一个数据的内存地址指针

  • 查询其中一个数据,必须遍历全部链表,查寻时间复杂度为O(n)

  • 链表中新增和删除数据性能比数组好很多,只需要更改对应对象的内存地址指针

Hash表

  • 快速查询并快速增删

  • 结构为数组类型,对key进行hash计算出数组下标,将对象放在对应下标里。因为hash计算可能冲突,所以数组内的元素是链表类型。当冲突后,就依次放到对应链表里。hash算法如果冲突率高,则会影响到查询、增删的效率。

栈、队列

  • 数组和链表都被称为线性表,栈就是在线性表的基础上加上限制条件--->后进先出。

  • 队列是在线性表的基础 上加了限制条件--->先进先出。

  • 二叉排序树:左子树所有节点均小于或等于它的根节点的值;右子树所有节点均大于或等于它的根节点的值。

  • 平衡二叉(排序)树:从任何一个节点出发,左右子节点深度之差绝对值不超过1。维持平衡就需要对树进行旋转操作,插入时最多只需要两次旋转就可以达到平衡,删除时需要维护从被删节点到根节点这条路径上的所有节点的平衡性,时间复杂度为O(logN)

  • 红黑(排序)树:

  • 每个节点只有两种颜色:红色、黑色

  • 根节点时黑色

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

  • 从根节点到叶子节点不会重复出现两个红色节点

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





  • 增加节点的时候,红黑树通过染色和旋转,保持红黑树满足定义

  • 红黑树VS平衡二叉树

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

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

  • 红黑树平衡性不如平衡二叉树,查询效率要低一些

跳表

  • 逻辑上就是给链接增加更粗力度的索引。

常用算法

递归算法(快速排序)

方法本身调用自己的行为称为递归,在不给退出递归条件会导致栈溢出。时间复杂度 n* log(n)

贪心算法

每一步都选择目前最优的算法称为贪心算法,目前最优最终结果不一定是最优的

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

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

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

  3. 重复这个过程,直到图中每个节点都这么做了。

  4. 计算最短路径。

动态规划解决背包问题

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

遗传算法解决背包问题

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

遗传算法以一种群体中的所有个体为对象,并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中选择、交叉和变异构成了遗传算法的遗传操作。参数编码,初始化群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

遗传算法的到的不是最优解。

网络通讯协议

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



  • 物理层:物理层负责数据的物理传输,计算机只能理解0、1的二进制数据,但在真正的通讯线路有光纤、电缆、无线各种设备。光信号和电信号以及无线电磁信号在物理层面都是不同的,这就是物理层要解决的问题。

  • 链路层:链路层就是将数据进行封装后交给物理层进行传输,主要将数据封装成帧,以帧为单位向物理层传输。有了帧,就可以在上面做验证、流量控制。

  • 网络层:网络层IP协议使得互联网应用根据IP地址就能访问目标服务器,请求离开APP后,到达运营商的交换机,交换机会根据这个IP地址进行路由转发。

  • 传输层:IP协议不是一个可靠的通讯协议,不会建立稳定的通许链路,并不保证数据一定送达。要保证通讯的稳定可靠,就需要传输层协议TCP

TCP协议是面向连接的、可靠的、面向字节流的传输层协议。TCP是通过以下机制保证了可靠性和强壮性:

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

  • 无错传输,使用检验和检测报文段段错误

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

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

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

  • 应用层:

  • http协议请求的7种方法

  • Get: 只读请求,请求处理过程不应该产生副作用。

  • Head: 和Get请求一样,只是只返回请求头

  • Post: 提交请求

  • Put: 上传请求

  • Delete: 删除URL标识的资源

  • Trace: 回显服务器收到的请求,用以测试或者诊断

  • Options: 请求服务器返回支持的所有http请求方法,测试服务器是否正常

  • http 响应的5种状态

  • 1xx:请求已经被服务器接收,继续处理

  • 2xx: 请求已成功被服务器接收、理解、并接收

  • 3xx:重定向,需要后续操作才能完成这一请求

  • 4xx:请求错误,请求含有词法错误或者无法被执行

  • 5xx: 服务器错误,服务器在处理某个正确请求时发生错误

  • http协议版本

  • http/1.0,客户端请求到资源后会关闭连接,并发量大的时候会导致频繁的创建、关闭TCP连接

  • http/1.1, 默认启用长连接模式,可以理解为半双工模式

  • http/2.0,服用tcp连接的方式不同,依然遵循请求-响应模式,但客户端发送多个请求和服务段发送多个响应没有顺序要求,这样避免了“队头堵塞”,又能更快获得响应下。

非阻塞网络I/O

阻塞网络BI/O:

在进行网络I/O操作的时候,用户线程会被一只阻塞,直到读/写操作完成。

非阻塞网络I/O:

I/O操作立即返回,发起线程不会阻塞等待。

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



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

数据库架构

  • 连接器:

数据库连接器会为每一个连接请求分配一块专用的内存空间用于会话上下文管理。建立连接对数据库而言是一个比较重的操作,因此一般应用在启动的时候会创建一批连接线程放在线程池里,当需要请求执行sql的时候就不需要再创建了。

  • 语法分析器:根据数据库sql规则,将sql语句解析为一棵树并判断是否符合语法规则

  • 语义分析与优化器

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

  • PrepareStatement:会预先提交带占位符的sql到数据库进行预处理,提前生存执行计划,在真正执行sql的时候,执行引擎可以直接执行,效率高一些,并可防止sql注入。

索引

  • 聚簇索引:聚簇索引的数据库记录和索引存储在一起。mysql数据库的主键就是聚簇索引,主键id和所在行记录存储在一棵B+树中

􏲮􏲯􏰯􏾕

  • 非聚簇索引:

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

  • 添加必要索引,优化sql查询性能

  • 谨慎添加索引,特别是生产环境

  • 添加索引的alter操作会消耗较多的时间(分钟级)

  • Alter操作期间,数据库所有的增删该全部阻塞。

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

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

  • int 4字节,biting 8字节,Timestamp 4字节 Datatime 8字节

数据库事务

事务特性ACID:

  • 原子性 (Atomicity) :事务要么全部完成,要么全部取消。如果事务崩溃,状态回到开始事务之前。

  • 隔离性(Isolation):如果两个事务T1,T2同时运行,事务T1,T2最终的结果是一致的,不管谁先结束,隔离性主要靠锁实现。

  • 持久性(Durability):一旦事务提交后,不管发生什了,数据要保持在数据库中。

  • 一致性:(Consistency):只有合法的数据才会被存到数据库中。

数据库事务日志:

进行事务操作时,事务日志文件会记录更新前的数据,然后再更新到数据库中的记录,如果全部成功则事务提交正常结束,如果失败那么整个事务就会根据执行之前记录的数据进行回滚。

  • LSN:一个按时间顺序分配的唯一事务记录日志序列号

  • TransID: 产生操作的事务ID

  • PageID:被修改的数据在磁盘中的位置

  • PrevLSN: 同一个事务产生的上一个日志记录的指针

  • UNDO:取消本次操作的方法,按照此方法回滚

  • REDO:重复本次操作方法

用户头像

小叶

关注

还未添加个人签名 2018.10.21 加入

还未添加个人简介

评论

发布
暂无评论
数据结构与算法以及网络与数据库总结