架构师训练营第八周总结

用户头像
养乐多
关注
发布于: 2020 年 07 月 29 日
架构师训练营第八周总结
  1. 数据结构与算法

  • 时间复杂度

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

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

  • 空间复杂度

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

  • NP问题

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

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

  • 数据结构:

  • 数组:空间连续,每个元素长度相同,通过存储空间偏移量计算确定位置

  • 链表:插入删除时间复杂度为O(1),访问元素时间复杂度为O(n),衍生数据结构为跳表

  • Hash表:数组+链表

  • 栈:先进后出,线程调用栈,栈帧,树的dfs遍历非递归

  • 队列:先进先出,树的bfs遍历

  • 树:

  • 二叉排序树:

  • 左子树上的所有节点的值小于等于根节点的值

  • 右子树上的所有节点的值大于等于根节点的值

  • 平衡二叉(排序)树

  • 完全平衡

  • 从任何一个节点出发,左右子树深度之差的绝对值不超过1

  • 通过旋转二叉树恢复平衡

  • 右右树:左旋

  • 左左树:右旋

  • 右左树:右左旋

  • 左右树:左右旋

  • 红黑树:

  • 近似平衡

  • 特点:

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

  • 根节点是黑色的

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

  • 从根节点到叶子节点,不会出现两个连续的红色的节点

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

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

  • 红黑树VS平衡二叉树

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

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

  • 红黑树的平衡性不如二叉平衡树,查询效率会差一些

  • 跳表

  • 常用算法

  • 穷举算法

  • 递归算法

  • 贪心算法

  • 动态规划

用户头像

养乐多

关注

还未添加个人签名 2019.11.12 加入

还未添加个人简介

评论

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