0%

算法分析之基本思想

算法是为解决某个具体问题设计的解题步骤,根据问题分类有:

  1. 排序
  2. 查找
  3. 字符串:字符串匹配等
  4. 图问题:对复杂关系的建模
  5. 组合问题:排列组合,选取满足目标的对象,比如成本最小等
  6. 几何问题:处理点、线、面等几何对象,应用于计算机图形学
  7. 数值问题:数学问题,比较解方程,计算定积分等

因算法依赖具体问题,局限性较强,但很多算法设计思想有相通之处,根据设计思想分类有:

  1. 蛮力法:比如 BFS,DFS,顺序遍历等,遍历所有解空间,找满足条件的解
  2. 分治法:
  3. 动态规划:主要是多阶段决策问题
  4. 贪心:图相关算法,最小生成树(Prim 算法和 Kruskal 算法),最短路径(dijkstra 算法)都属于贪心算法

一些个人总结:
不论什么问题,第一步都可以将问题规模降到最低,然后求解,然后问题规模再变大一点,再去求解
根据这个过程,就可以利用不同的设计技巧

  1. 如果增大问题规模,求解需要使用原来已求解的结果,这就是动态规划,保存每个阶段的结果,递推下去,就可以找到最终解
  2. 如果增大问题规模,求解过程不依赖原来已求解的结果,这就是分治,分成独立的子问题,分别求解,然后合并解就是最终解
  3. 如果增大问题规模,

一些个人文章:
动态规划的解释
labuladong 个人文章
程序员小吴