几个基本的算法设计方法

1)、递归和递推。递归和递推是学习算法设计的第一步。递归算法是把大问题分解成相对较小的问题的过程,而递推就是从小问题逐步推导出大问题的过程。无论递归还是递推,都应该有初始状态。

2)、搜索、枚举及优化剪枝。搜索在所有算法中既是最简单也是最复杂的算法。说它简单,是因为算法本身并不复杂,实现容易;说它最复杂,是因为要对搜索的范围进行一定的控制,不然就会出现超时等问题。搜索技术主要包括广度优先搜索和深度优先搜索。当其余算法都无法对问题进行求解时,搜索或许是唯一可用的方法。搜索是对问题的解空间进行遍历的过程。有时问题解空间相当庞大,完全遍历解空间是不现实的,此时就必须充分发掘问题所包含的约束条件,在搜索过程中应用这些条件进行剪枝,从而减少搜索量。

3)、动态规划(简称DP)。动态规划的特点是能够把很复杂的问题分解成一个个阶段来处理的递推方法,动态规划必须符合两个特点:无后效性(一个状态的抉择不会影响到更大问题的状态的抉择)及最优化原理(一个大问题的最优性必须建立在其子问题的最优性之上)。动态规划是竞赛中经常出现的的类型,而且变化很大(有线性DP,环形DP,树形DP等),难易跨度大,技巧性强,甚至还有DP的优化等问题。

4)、贪心。贪心算法是所谓的“只顾眼前利益”的算法。其具体策略是并不从整体最优上加以考虑,而是选取某种意义下的局部最优解。当然使用贪心算法时,要使得到的结果也是整体最优的。

5)、分治、构造等。分治就是把问题分成若干子问题,然后“分而治之”;构造是指按照一定的规则产生解决问题的方法。这两种算法都是在合理的分析题目后,通过一定的规律性推导,从而解决问题。快速排序可以认为是利用了分治法。

原文地址:https://www.cnblogs.com/zhaoshuireshui/p/3655455.html