作业二：根据当周学习情况，完成一篇学习总结

算法

时间复杂度



• 多项式时间复杂度：O(1),O(logn),O(n^a)

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

空间复杂度

算法在执行过程中需要用到的存储空间大小。

NP问题

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

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

• NP-hard问题：比NP问题更难的问题。（例如二元一次方程是比一元一次方程更难的方程）

• NP完全问题：是一个NP-hard问题，也是NP问题

数据结构

数组



1. 必须连续内存空间

2. 只能存放相同类型（数组记录内存地址公式：当前下标地址 = 首地址+ 类型大小*下标数）

3. 随机快速读写特性，根据下标访问数据时间复杂度O(1)

4. 查找时间复杂度O(n)

链表



1. 不要求连续内存空间

2. 需要额外空间在存储下一个节点的内存地址

3. 查找时间复杂度O(n)

数组链表组合

将数组和链表组合，实现快速查找和快速增删。

Hash表



容量为8的数组，要将数据放到数组中，实现插入和查询的时间复杂度都是O(1)。做法如下：

1. 获取数据的hashcode

2. 该数据在数组中的下标为：hashcode%8

3. 利用数组随机快速读写的特写。插入位置为hashcode%8，查询数据位置，通过hashcode%8算出下标，直接通过下标访问。

如果存在两个或两个以上的数据计算出来的hashcode是相同的，这种情况称为hash冲突

Hash冲突

为了解决hash冲突，可以使用数组和链表组合，数据结构如下：



数组中不再存放具体的数据，而是存放链表的首地址。当数据存在hash冲突时，直接将数据插入到该数组下标的链表中。该数据结构就是HashMap的数据结构（HashMap当hash冲突达到指定值会转换成红黑树，因为链表的查询复杂度是O(n)）



栈

数组和链表都是线性表，而栈是在线性表的基础上，加上了操作限制（先进后出）。



队列

操作受限的线性表，先进先出。



树

二叉排序树

左子树节点 < 根节点 < 右子树节点

不平衡二叉树



平衡二叉树

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

旋转二叉树恢复平衡



红黑（排序）树

树节点只有红色和黑色两种颜色

根节点是黑色的

每个叶子节点（NIL）都是黑色的空节点

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

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



操作案例



红黑数 VS 平衡二叉树

1. 红黑树在添加或删除元素时，最多只需要旋转3次。时间复杂度0(1)

2. 红黑树的平衡性不如平衡二叉树，所以红黑树的查询效率会低于平衡二叉树

跳表



算法

穷举算法

递归算法

• 快速排序

• 归并排序

贪心算法

迪杰斯特拉算法







动态规划

一个能装4磅的背包，如何装下最大价值的物品？



每个动态规划算法都从一个网格开始，背包问题网格如下：



解决方案如下：