Week 08 总结 - 数据结构和算法

用户头像
鱼_XueTr
关注
发布于: 2020 年 07 月 29 日
Week 08 总结- 数据结构和算法
  1. 时间复杂度和空间复杂度

  • 时间复杂度:算法执行语句的次数

  • 空间复杂度:运行过程中占用内存空间打大小



  1. NP问题

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

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

  • NP-hard: 比NP问题更难的问题(NP问题的解法可以规约到NP-hard问题的解法)



  1. 数组

  • 内存中的一块连续内存,存储元素类型相同,根据索引访问的时间复杂度O(1),其余操作时间复杂度为O(n)



  1. 链表

  • 链表可以使用零散的内存空间存储数据。查找复杂度O(n),增删O(1)



  1. Hash表

  • 访问快,增删快

  • 占用内存大

  • 会发生key冲突



  1. 栈和队列

  • 栈:先进后出

  • 队列:先进先出



  • 二叉排序树:左子树上所有节点的值均小于或等于它的根节点的值,右子树上所有节点的值大于或等于它的根节点的值。

  • 旋转二叉树恢复平衡:插入时,最多只需要两次旋转就会重新恢复平衡,删除时,需要维护从被删节点到根节点这条路径上所有节点的平衡性,时间复杂度O(logN)

  • 红黑(排序)树:每个节点只有两种颜色:红色和黑色,根节点是黑色。每个叶子节点都是黑色的空节点,从根节点到叶子节点,不会出现两个连续的红色节点。从任何一个节点出现,到叶子节点,这条路径上都是有相同数目的黑色节点。增删节点的时候,红黑树通过染色和旋转,保持红黑树满足定义。



  1. 跳表

  • 结合数组和链表的有点



  1. 常用算法

  • 穷举算法

  • 递归算法

  • 贪心算法

  • 动态规划



  1. 贪心算法

  • 背包问题: 小偷背了一个4磅背包去商城偷东西,将那些商品放入背包才能收益最大化。



  1. 改进贪心算法-迪杰斯特拉算法(最快路径)

  • 找出最便宜的节点,即可在最短时间内到达节点

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

  • 重复这个过程,知道对图中的每个节点都这样做了

  • 计算最短路径



  1. 动态规划解决背包问题

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



  1. 遗传算法解决背包问题

  • 遗传算法:模拟自然进化过程搜索最优解的方法。选择,交叉,变异,构成了遗传算法的遗传操作

  • 遗传算法五个要素:参数编码,初始群体的设定,适应度函数的设计,遗传操作设计,控制参数设定

  • 遗传算法得到的不是最优解



  1. 遗传算法-选择算法

  • 轮盘赌选择:回放式随机采样,每个染色体进入下一代的概率等于它的适应值与整体适应值和比例

  • 随机竞争选择:每次按轮盘赌选择一个个体,然后让这两个个体进行竞争,适应度高被选中,反复

  • 均匀排序:对群体中的所有个体按适应度大小进行排序,基于这个排序来分配各个个体被选中的概率



用户头像

鱼_XueTr

关注

还未添加个人签名 2019.04.19 加入

还未添加个人简介

评论

发布
暂无评论
Week 08 总结- 数据结构和算法