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