第八周总结

1. 时间复杂度

不是计算程序具体运行的时间，而是算法执行语句的次数

1. 空间复杂度

一个算法在运行过程中临时占用的存储空间大小的量度。

1. NP问题

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

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

NP-hard: 比NP更难的问题 （NP问题可以规约到NP-hard问题）

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

1. 数据结构

• 数组

• 链表

• Hash表

• 栈

• 队列

• 树

二叉排序树

平衡二叉树

红黑树

红黑树 VS 平衡二叉树

a. 红黑树最多只需三次旋转就会重新达到红黑平衡，时间复杂度为O(1)

• 递归算法（快速排序）

方法本身调用自己的行为称为递归，在不给退出递归条件会导致栈溢出。时间复杂度 n* log(n)

• 贪心算法

每一步都选择目前最优的算法称为贪心算法，目前最优最终结果不一定是最优的

• 改进贪心算法-迪杰斯特拉算法（最快路径）

a. 找出“最便宜”节点，即可在最短时间内到达的节点。

b. 更新该节点的邻居开销，检查是否有前往它们更短的路径，如果有，就更新其开销。

c. 重复这个过程，直到图中每个节点都这么做了。

d. 计算最短路径。

• 动态规划解决背包问题

通过找到合适的角度，将所求解的目标值在某（几）个维度上展开，将一个大问题拆解为若干小问题，小问题的最优解，寻找大问题的最优解

• 遗传算法解决背包问题

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的算法。

遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中选择、交叉和变异构成了遗传算法的遗传操作。参数编码，初始化群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

遗传算法的到的不是最优解。