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

用户头像
Anrika
关注
发布于: 2020 年 07 月 29 日
架构师训练营 - 第八周 - 学习总结

数据结构和算法

时间复杂度和空间复杂度:

数组:是一种在连续内存空间上存储相同类型数据的数据结构,可通过数组名和下标进行数据的访问和更新。数组的读写时间复杂度是O(1)

链表:是利用零散的内存空间存储数据的,每个数据节点都是由数据本身和下一个数据的地址指针组成,查询链表数据需要遍历链表,因此链表的读写数据的时间复杂度是O(n)。

Hash表:是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。

:是一种基于线性表的数据结构,数据先入后出。

队列:队列是一种特殊的线性表,特殊之处在于它只允许在表的前端进行删除操作,而在表的后端进行插入操作,和栈一样,队列是一种操作受限制的线性表。先进先出。

树:最常见的就是二叉树,二叉树(Binary Tree)是一个有根树,并且每个节点最多只有2科子树(即二叉树中不存在度大于2的结点),并且二叉树的子树有左右之分,其次序不能任意颠倒。二叉树又分为完全二叉树、满二叉树、平衡二叉树、红黑树等。

  • 二叉树

二叉树和树的区别树节点的子节点只有两个,一个左节点,一个右节点。

  • 二叉排序树

二叉排序树要求节点的左节点总是小于父节点,右节点总大于父节点。

二叉排序树在最差情况会退化为链表。

  • 平衡二叉排序树

平衡二叉树在二叉排序树上进行优化,平衡二叉排序树丛任意节点开始出发,左右子树的深度想差不会超过1,平衡二叉排序树的搜索性能很好,但平衡过程计算很差。

  • 红黑树

红黑树在平衡二叉树上继续进行了优化,红黑树保证的要求是大体平衡,而不是完全平衡,在搜索性能和插入添加性能上都比较均衡。红黑树的实现非常复杂。

  • 跳跃表

由于红黑树实现非常复杂,所以延伸出了跳表,跳表是从有序链表上不断提取部分节点出来组成一个新链表,然后根据新链表再次提取部分节点形成链表,多次以后,最后顶层的链表应该只有两个节点,本质上也是一个二分查找法,这个查询效率和红黑树差不多,但是使用了额外的一倍的空间,所以只要空间允许,跳跃表是一种简单有效的数据结构。

常用算法

  • 穷举算法

  • 递归算法

  • 贪心算法

  • 动态规划



发布于: 2020 年 07 月 29 日 阅读数: 32
用户头像

Anrika

关注

还未添加个人签名 2018.08.21 加入

还未添加个人简介

评论

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