有哪些常见的算法思想
分治算法 :分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解决。
动态规划算法: 通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。和分治算法最大的差别:适用于动态规划算法求解的问题经过分解后得到的子问题往往不是相互独立的,而是下一个子阶段的求解是建立在上一个子阶段的解的基础上的。
贪心算法:保证每次操作都是局部最优的,并且最后得到的结果是全局最优的
二分法: 比如重要的二分法,比如二分查找;二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
搜索算法: 主要包含BFS,DFS
Backtracking(回溯): 属于 DFS, 回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法