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



时间复杂度、空间复杂度

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

NP问题：能在多项式时间复杂度内验证的问题

NP-hard问题： 一类NP问题的解法

NP完全问题：是NP-hard问题，也是NP问题



• 数据结构

数组：

连续空间、相同类型 ->随机查找快、增删慢

链表：

零散空间、指针指向下一个数据 ->随机查找慢、增删快

数组+链表：

数组中保存链表的头结点

Hash表：Key计算hashcode，从数组中查找

Hash冲突：形成链表

栈：

后进先出的线性表

数组、链表都能实现

队列：

先进先出

消息队列

应用：

由近及远查找符合条件的人：好友入队，出队列时，把好友的好友入队

搜索最短路径：搜索起点到终点的最小步数（路径的步长一致）

树：

二叉排序树

->（不平衡退化为链表）->

平衡二叉排序树：左右子树深度差不超过1。查找效率高

->(旋转恢复平衡，代价大)->

红黑树：增删效率高、查找效率差

根为黑色、叶子为黑色空节点NIL

不会出现连续的红色、

任何节点到其叶子节点的路径上黑色节点数相同

->（染色和旋转，最多三次）



跳表：

有序链表 - 创建上层稀疏的链表

查找时，从稀疏的链表开始查找



• 算法：

穷举算法

递归算法：可能栈溢出

贪心算法：每一步的当前最优解，不一定是全局最优解

迪杰斯特拉算法：计算起点到每个节点的最短路径

动态规划：分治，子任务之间有关联（公共子问题）

遗传算法：得到的不是最优解

背包问题：

基因编码（0未选择，1选择）与染色体（基因组合）

适应函数（总价值最大）与控制参数（不能超过总重量）

选择算法（根据适应值选择可以遗传的染色体及繁殖次数）

交叉遗传（不同的交叉点，染色体变动）、突变

收敛：如果连续几代都没有更强的染色体



• 网络模型



发送：层层封包

接收：层层解包



http：队头堵塞



• Socket - 是支持TCP/IP协议的网络通信的基本操作单元。

主线程：负责建立连接

多线程：一个连接 - 一个Socket - 一个线程

线程池：减少创建线程的开销



• Java NIO

Channel ：对应socket连接

Selector选择器 -- 检查Channel通道的事件 -- 执行selectionkey操作（write/read/accept/connect）

• 系统I/O复用

select/poll：轮询所有的socket

epoll：设备就绪后执行回调函数，将自己加入就绪链表；epoll遍历就绪链表



• 数据库

连接器：建立连接比较消耗时间；

语法分析器：

语义分析与优化器：复杂嵌套的SQL进行语义转化

执行计划：



B-/B+树：

B+树的所有数据都在叶子节点上。主要用来构建索引

聚簇索引：B+树；数据库记录和索引存储在一起。Mysql主键。

非聚簇索引：B+树；数据库记录主键和索引存储在一起。



谨慎使用索引：

索引的修改会消耗较长的时间；

索引的修改会阻塞数据库的所有操作（增删改查）

删除不用的索引，避免开销；

小数据类型创建索引。