架构师训练营第 8 周总结
数据结构与算法
算法复杂度
时间复杂度
并不是计算程序具体的运行时间而是算法执行语句的次数
多项式时间复杂度O(1)、O(logn)、O(n)、O(nlogn)、O(n2 )
非多项式时间复杂度
空间复杂度
一个算法在运行过程中临时占用存储空间大小的度量
O(n)表示需要临时存储n个数据
NP问题
P: 能在多项式时间复杂度内解决的问题
NP:能在多项式时间复杂度内验证答案正确与否的问题
NP ?= P
NP-hard:比NP更难的问题(NP问题的解法可以规约到NP-hard问题的解法)
NP完全问题,是一个NP-hard问题,也是一个NP问题
数据结构
数组
创建数组必须在内存中一块连续的空间
数组中必须存放相同的数据类型
随机读写是数组的一个重要特性,根据数组下标访问数据,时间复杂度为O(1)
链表
可以使用零散的内存空间存储数据
链表中的每个数据元素都必须包含指向下一链表元素的指针
链表查找的时间复杂度为O(n)
链表中增删数据的性能比数组要好
数组链表结合,实现快速查找和快速增删
哈希表
如何快速访问数据,又快速增删数据
哈希表key冲突,开放寻址法,链表法,红黑树
栈
后进消除
应用:线程调用栈
队列
先进先出
应用场景生产者消费者寻找n度好友关系,广度优先遍历最短路径 dijkstra
树
二叉排序树
不平衡的二叉排序树
平衡的二叉排序树
旋转恢复树的平衡
红黑树
红黑树 vs 二叉排序树
跳表
比红黑树实现更简单
适合范围查找
常用算法
递归算法
时间复杂度:nlog(n)
贪心算法
背包问题,未必能找到最优解
改进贪心算法 - dijkstra
动态规划
倒推,dp方程
背包问题
遗传算法
背包问题
也不一定能找到最优解
网络通讯协议
OSI七层模型和TCP四层模型
应用层 表示层 会话层 传输层 网络层 数据链路层 物理层
非阻塞IO
评论