算法

这边简单跟大家介绍一下一些算法名词代表的含义.

动态规划(Dynamic Programming)

主要思想:

1. 将问题分解为多个子问题
2. 子问题之间存在重叠性质,可以存储子问题的结果,避免重复计算
3. 根据子问题的结果,逐步合并得到原问题的解

动态规划方法具有以下特点:

• 分阶段求解
• 存储中间结果
• 自底向上
• 重复子问题

应用动态规划一般需要满足以下条件:

• 问题能分解为子问题
• 子问题之间存在重叠子问题
• 存在最优子结构
• 能利用中途结果推导最终解

常见的动态规划问题有背包问题、最长公共子序列等.相比暴力法,动态规划通过避免重复计算和利用已有结果,可以大幅减少计算量,获得多项式时间复杂度.

二分查找(Binary Search)

是一种在有序数组中查找目标值的算法,其思想是:

1. 每次将查找区间分为二分,取中间位置的元素与目标值比较
2. 如果中间元素等于目标值,则找到目标元素返回
3. 如果中间元素大于目标值,则目标值在左区间,将右边界调整为中间元素索引-1
4. 如果中间元素小于目标值,则目标值在右区间,将左边界调整为中间元素索引+1
5. 重复步骤 1-4,直到找到目标元素或者区间被缩小为不存在

二分查找的前提是数组必须有序.其时间复杂度为 O(logN).

二分查找算法步骤:

1. 初始化左右指针 l = 0, r = N-1
2. 循环直到 l > r
   • 计算 mid = (l + r) / 2
   • 比较 A[mid] 与 target
   • target 在左区间:r = mid - 1
   • target 在右区间:l = mid + 1
3. 如果找到 target,返回索引,否则返回-1

相比顺序查找的 O(N),二分查找大大提高了查找效率.

贪心算法(Greedy Algorithm)

基本思想是:

1. 每一步都选择当前最优或局部最优的解
2. 通过累积当前最优解获得全局最优解

其具体做法是:

• 建立数学模型,将问题抽象出状态、选择标准等元素
• 确定每一步的局部最优选择,得到选择标准
• 设计贪心算法规则,只做当前最优决策
• 证明该算法能通过局部最优获得全局最优

贪心算法的特点:

• 每步都做出一个选择,不能回退
• 依赖问题具备最优子结构
• 可以快速直接求解,效率高
• 无法得到最优解的问题不能使用贪心算法

常见的贪心算法问题有:求最小花费、求最少硬币找零等.总之,贪心算法依靠局部最优推出全局最优,在一些问题中可以得到整体最优解.但也依赖于问题本身的性质,具有一定的局限性.

回溯修正(Backtracking)

常用于求解组合优化问题,其基本思想是:

1. 递归枚举所有的可能解
2. 当发现不是最优解时进行回溯,修改选择并继续递归搜索
3. 通过递归搜索空间,找出问题的最优解

回溯修正算法的设计步骤:

1. 定义问题的解空间,表示可能的解集合
2. 确定易于搜索的解空间结构,如树、图等
3. 确定递归遍历解空间的规则,以及找到解的条件
4. 回溯时设置适当的数据结构进行恢复
5. 设计回溯修正的规则,当发现不是最优解进行恢复

回溯法可以有效解决组合优化问题,但其复杂度较高,需要根据具体问题进行优化设计.相比暴力法,回溯法通过增加回溯将指数级复杂度问题,降低为多项式复杂度问题.