架构师训练营第八周总结

时间复杂度

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

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

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

跳表

常用算法

穷举算法

递归算法

贪心算法

动态规划