Week 08 总结 - 数据结构和算法
时间复杂度和空间复杂度
时间复杂度:算法执行语句的次数
空间复杂度:运行过程中占用内存空间打大小
NP 问题
P:能在多项式时间复杂度内解决的问题
NP:能在多项式时间复杂度内验证答案正确与否的问题
NP-hard: 比 NP 问题更难的问题(NP 问题的解法可以规约到 NP-hard 问题的解法)
数组
内存中的一块连续内存,存储元素类型相同,根据索引访问的时间复杂度 O(1),其余操作时间复杂度为 O(n)
链表
链表可以使用零散的内存空间存储数据。查找复杂度 O(n),增删 O(1)
Hash 表
访问快,增删快
占用内存大
会发生 key 冲突
栈和队列
栈:先进后出
队列:先进先出
树
二叉排序树:左子树上所有节点的值均小于或等于它的根节点的值,右子树上所有节点的值大于或等于它的根节点的值。
旋转二叉树恢复平衡:插入时,最多只需要两次旋转就会重新恢复平衡,删除时,需要维护从被删节点到根节点这条路径上所有节点的平衡性,时间复杂度 O(logN)
红黑(排序)树:每个节点只有两种颜色:红色和黑色,根节点是黑色。每个叶子节点都是黑色的空节点,从根节点到叶子节点,不会出现两个连续的红色节点。从任何一个节点出现,到叶子节点,这条路径上都是有相同数目的黑色节点。增删节点的时候,红黑树通过染色和旋转,保持红黑树满足定义。
跳表
结合数组和链表的有点
常用算法
穷举算法
递归算法
贪心算法
动态规划
贪心算法
背包问题: 小偷背了一个 4 磅背包去商城偷东西,将那些商品放入背包才能收益最大化。
改进贪心算法-迪杰斯特拉算法(最快路径)
找出最便宜的节点,即可在最短时间内到达节点
更新该节点的邻居的开销,检查是否有前往它们的更短路径,如果有,就更新其开销
重复这个过程,知道对图中的每个节点都这样做了
计算最短路径
动态规划解决背包问题
通过找到合适的角度,将所求解的目标值在某(几)个维度上展开,将一个大问题拆解为若干小问题,小问题的最优解,寻找大问题的最优解
遗传算法解决背包问题
遗传算法:模拟自然进化过程搜索最优解的方法。选择,交叉,变异,构成了遗传算法的遗传操作
遗传算法五个要素:参数编码,初始群体的设定,适应度函数的设计,遗传操作设计,控制参数设定
遗传算法得到的不是最优解
遗传算法-选择算法
轮盘赌选择:回放式随机采样,每个染色体进入下一代的概率等于它的适应值与整体适应值和比例
随机竞争选择:每次按轮盘赌选择一个个体,然后让这两个个体进行竞争,适应度高被选中,反复
均匀排序:对群体中的所有个体按适应度大小进行排序,基于这个排序来分配各个个体被选中的概率
评论