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

数据结构和算法

时间复杂度和空间复杂度：

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

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

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

栈：是一种基于线性表的数据结构，数据先入后出。

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

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

• 二叉树

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

• 二叉排序树

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

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

• 平衡二叉排序树

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

• 红黑树

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

• 跳跃表

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

常用算法

• 穷举算法

• 递归算法

• 贪心算法

• 动态规划