架构师训练营 - 学习总结 - 第八讲

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

数据结构和算法

时间复杂度

算法执行语句的次数,并不是运行时间。



空间复杂度

运行过程中临时占用存储空间

O(n)指需要临时存储n个数据。这里具体大小要看具体数据。



数组

连续空间、相同类型、查找复杂度为O(1)、插入新数据时间复杂度为O(n)



链表

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

只能遍历查找。

查找复杂度为O(N),插入新数据时间复杂度为O(1)



Hash表

数组+链表

数组存储链表的头指针,查找复杂度为O(1),插入新数据时间复杂度为O(1)



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

栈就是在线性表基础上增加操作限制条件:后进先出



队列

先进先出



红黑树和平衡二叉树

红黑树最多旋转3次就可以重新平衡,时间复杂度O(1)

大量增删情况下、红黑树效率高

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



红黑树太麻烦了,常用跳表替代。



常用算法

穷举算法

递归算法

贪心算法:

动态规划



背包问题,用贪心算法得到较优解。

迪杰斯特拉算法,改进的贪心算法。



背包问题用动态规划,寻找最优解



遗传算法

通过模拟自然进化过程搜索最优解的方法

物品是否选择设定为基因

例如:

100100:选择物品1,4

101011:选择物品1,3,5,6

第一步

选择适应度函数:商品总价值

选择控制函数:总重量,淘汰超重的基因

第二步

选择算法:

轮盘赌选择:一种回放式随机采样,每个染色体进入下一对待的概率等于它的适应度值与整体适应度值得比例

随即竞争选择:每次按轮盘赌选择一对个体,然后然后让这两个个体进行竞争,适应度高的被选中,如此反复,直到选满位置。

均匀排序:对群体中的所有个体按适应度大小进行排序,基于这个排序来分配各个个体被选中的概率。

 第三步

产生后代:

交叉遗传,选择点位互换生成新的染色体。

之后

循环迭代,记录每一轮价值最大染色体。如果连续几代都没有出现更强的染色体,算法收敛。



遗传算法不一定得到最优解,但是得到较优解时间复杂度O(1)。



网络与数据库

七层协议和TCP/IP的四层协议

3112从上往下对应



HTTP/3,使用QUIC协议。



非阻塞网络I/O

典型方式:

一个socket一个线程,建立连接用一个专门的线程。



Java NIO(New I/O)

阻塞,不是Non-Block的N

关键点:Selector.select();



数据库架构

连接器,语法分析器,语义分析与优化器,执行引擎



prepareStatement 提前进行预处理,生成执行计划,效率更高

可以防止SQL注入。



不要增加无必要的索引,增删会消耗时间。无查询的字段不需要索引。



数据库事务日志

实务操作,记录更新前的数据。UNDO时全部写回。



用户头像

吕浩

关注

还未添加个人签名 2018.04.27 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 - 学习总结 - 第八讲