admin管理员组

文章数量:1583583

算法图解笔记

  • 分治策略
  • 散列函数
  • 广度优先搜索
  • 狄克斯特拉算法
  • 动态规划

算法图解（pdf版） 链接：https://pan.baidu/s/1FJvija2NNmhOSpd7D3yE_g 提取码：bwcm

分治策略

分治策略（分而治之）是一种解决问题的思路，使用递归实现

工作原理：

  1. 找出简单基线条件（递归中的概念，基线条件指函数不再调用自己；递归条件指函数调用自己）
  2. 缩小问题规模使接近基线条件（编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。）

代表算法：二分查找，快排

散列函数

散列表适用场景

  • 模拟映射关系
  • 防止重复
  • 数据缓存

注意的点

  • 冲突很糟糕，应使用可以最大限度减少冲突的散列函数（冲突过多会影响数据查找、删除速度；严重时会退化为链表）
  • 一旦填装因子超过0.7，就该调整散列表的长度

广度优先搜索

广度优先是一种用于图的查找算法，一般用来帮助解决两类问题：

  1. 有无路径问题（从节点A出发，有到节点B的路径吗？）
  2. 最短路径问题（从节点A触发，前往节点B哪条路径最短？）

注意点

  • 对于寻找最短路径的问题，可尝试使用图来建立模型，再使用广度优先搜索来解决问题
  • 有向图中的边为箭头，箭头的方向指定了关系的方向
  • 无向图中的边不带箭头，其中的关系是双向的
  • 你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列
  • 对于检查过的人，务必不要再去检查，否则可能导致无限循环（节点间的相互引用）

狄克斯特拉算法

在介绍迪克斯特拉算法前，先介绍一些基础概念
每条边都有关联数字的图，这些数字称为权重

带权重的图称为加权图，不带权重的图称为非加权图

图中可能有环

本文标签： 下载地址算法笔记PDF

版权声明：本文标题：算法图解笔记（附PDF下载地址） 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dongtai/1727922008a1138303.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。