算法基础 - 常见算法和比较

参考资料

算法思想

  • 穷举法

    • 列出问题所有可能解的情况，从中搜索正确答案。

  • 分治算法

    • 将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

  • 递推算法

    • 从已知的条件出发，逐步推算出问题的解。每一次推导的结果可以作为下一次推导的开始，这似乎跟迭代、递归的思想有点类似，不过递推的范畴要更广一些。

  • 递归算法

    • 把问题转化成规模更小的同类子问题，先解决子问题，再通过相同的求解过程逐步解决更高层次的问题，最终获得最终的解。即在函数或者子过程的内部，直接或间接的调用自己算法。
    • 递归调用分为两种情况：
      • 直接递归，即在方法中调用方法本身
      • 间接递归，即间接地调用一个方法

  • 动态规划算法

    • 每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

  • 贪心算法

    • 对问题求解时，保证每次操作都是局部最优的，并且最后得到的结果是全局最优的

  • 回溯算法

    • Backtracking(回溯)属于 DFS。实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
    • 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法

  • 模拟算法

    • 许多真实场景下，由于问题规模过大、变量过多等因素，很难将具体的问题抽象出来，也就无法针对抽象问题的特征来进行算法的设计。这个时候，模拟思想或许是最佳的解题策略。
    • 模拟的过程就是对真实场景尽可能的模拟，然后通过计算机强大的计算能力对结果进行预测。这相较于上述的算法是一种更为宏大的思想。在进行现实场景的模拟中，可能系统部件的实现都需要上述几个算法思想的参与。

算法比较

递推和递归的比较

*「递」的理解可以是逐次、逐步。在递推中，是逐次对问题进行推导直到获得最终解。而在递归中，则是逐次回归迭代，直到跳出回归。

暴力递归和动态规划

暴力递归

  1. 把问题转化为规模小的同类问题的子问题;
  2. 有明确不需要继续进行递归的条件Cbase case);
  3. 有当得到了子问题的结果之后的决策过程;
  4. 不记录每一个子问题的解。

动态规划

  1. 从暴力递归中来;
  2. 将每一个问题的解记录下来，避免重复计算;
  3. 将暴力递归的过程，抽象成状态表达;
  4. 并且存在化简状态表达，使其更加间洁的可能。

先写出尝试版本，分析可变参数，哪些参数可以表示子返回状态，即几个可变参数，生成几维表，把终止状态在表中写出来，回到base case中不依赖的位置填好，普遍位置需要哪些位置还回去，就是填表顺序。

动态规划

通常用于解决计数、求最值、求存在性的问题。

  1. 确认状态
  2. 转移方程
  3. 初始条件和边界情况
  4. 计算顺序
Last Updated:
Contributors: klc407073648