架构师训练营第 8 周总结

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

数据结构与算法



算法复杂度



时间复杂度



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

  • 多项式时间复杂度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



用户头像

Season

关注

还未添加个人签名 2019.09.28 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第8周总结