算法思想

算法基本思想

在计算机科学中，常用的算法设计思想包括以下几种：

• 贪心算法：

  • 贪心算法是一种简单而有效的算法设计思想，其核心思想是通过每一步选择最优的局部解，最终得到全局最优解。贪心算法通常适用于那些具有最优子结构的问题，即问题的最优解可以通过局部最优解推导得到。
  • 贪心算法通常用于最优化间题，我们做出一组选择来达到最优解。贪心算法的思想是每步选择都追求局部最优。一个简单的例子是找零间题：为了最小化找零的硬币数量，我们反复选择不大于剩余金额的最大面额的硬币。贪心方法对很多间题都能求得最优解，而且速度比动态规划方法决得多。但是，我们并不总能简单地判断出贪心算法是否有效。

• 分治算法：分治算法是一种将问题划分成多个子问题来求解的算法思想。该方法通常通过递归的方式，将原问题分解为更小的子问题，然后将子问题的解合并起来得到原问题的解。分治算法通常适用于那些可以划分为多个相似的子问题的问题，如归并排序和快速排序等。

• 动态规划算法：

  • 动态规划算法是一种通过将问题划分为多个子问题来求解的算法思想，但与分治算法不同的是，它通常使用迭代的方式来求解子问题，并将子问题的解保存下来，以避免重复计算。动态规划算法通常适用于那些具有重叠子问题和最优子结构的问题，如背包问题和最长公共子序列问题等。
  • 动态规划通常用来解决最优化间题，在这类间题中，我们通过做出一组选择来达到最优解。在做出每个选择的同时，通常会生成与原间题形式相同的子间题。当多千一个选择子集都生成相同的子间题时，动态规划技术通常就会很有效，其关键技术就是对每个这样的子问题都保存其解，当其重复出现时即可避免重复求解。

• 回溯算法：回溯算法是一种通过逐步构建可能的解来求解问题的算法思想。该方法通常通过递归的方式，将问题转化为子问题，然后构建可能的解，并检查其是否满足问题的要求。如果不满足要求，则撤销上一步并继续搜索下一种可能的解。回溯算法通常适用于那些求解所有可能解的问题，如八皇后问题和旅行商问题等。

• 分支限界算法：分支限界算法是一种通过逐步构建可能的解来求解问题的算法思想。该方法通常通过将问题的解空间划分为多个子空间，并为每个子空间定义一个界限值，然后按照某种策略搜索子空间。分支限界算法通常适用于那些具有可行解和最优解的问题，如旅行商问题和0/1背包问题等。

• 摊还分析：

  • 摊还分析方法分析一类特定的算法，这类算法执行一组相似的操作组成的序列。摊还分析并不是通过分别分析每个操作的实际代价的界来分析操作序列的代价的界，而是直接分析序列整体的实际代价的界。这种方法的一个好处是，虽然某些操作的代价可能很高，但其他很多操作的代价可能很低。换旬话说，很多操作的运行时间都会在最坏清况时间之内。摊还分析并不仅仅是一种分析工具，它还是一种思考算法设计的方式，因为算法设计和算法运行时间的分析常常是交织在—起的。

以上是常用的算法设计思想，不同的算法和情况可能适用不同的方法。在实际应用中，通常需要结合具体的问题选择最合适的方法进行设计。

分治算法

分治算法是一种将问题划分成多个子问题来求解的算法思想。该方法通常通过递归的方式，将原问题分解为更小的子问题，然后将子问题的解合并起来得到原问题的解。分治算法通常适用于那些可以划分为多个相似的子问题的问题，如归并排序和快速排序等。

分治算法 - 思路

在分治策略中，我们递归地求解一个问题，在每层递归中应用如下三个步骤：

• 分解(Divide)步骤将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
• 解决(Conquer)步骤递归地求解出子问题。如果子问题的规模足够小，则停止递归，直接求解。
• 合井(Combine)步骤将子问题的解组合成原问题的解。

当子问题足够大，需要递归求解时，我们称之为递归情况(recursive case)。 当子问题变得足够小，不再需要递归时，我们说递归已经＂触底“，进入了基本情况(base case)。

分治算法 - 递归式

三种求解递归式的方法，即得出算法的""或""渐近界的方法：

• 代入法我们猜测一个界，然后用数学归纳法证明这个界是正确的。
• 递归树法将递归式转换为一棵树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式。
• 主方法 可求解形如下面公式的递归式的界：
  • ，其中是一个给定的函数。
  • 这种形式的递归式很常见，它刻画了这样一个分治算法：生成个子问题，每个子问题的规模是原问题规模的，分解和合并步骤总共花费时间为。

其他情况，偶尔会遇到不是等式而是不等式的递归式：

• 如果不等式为，则这种递归式仅描述了的一个上界，因此可以用符号而不是符号来描述其解。
• 如果不等式为，则这种递归式仅描述了的一个下界，因此可以用符号来描述其解。

分治算法 - 被忽略的技术细节

当声明、求解递归式时，我们常常忽略向下取整、向上取整及边界条件。

• 向下取整、向上取整及边界条件：
  • 如果对个元素调用MERGE-SORT，当为奇数时，两个子问题的规模分别为和，准确来说都不是，因为当是奇数时，不是一个整数。技术上，描述MERGE-SORT最坏情况运行时间的准确的递归式为:
• 忽略数据规模：
  • 由于对于一个常量规模的输入，算法的运行时间为常量，因此对于足够小的，表示算法运行时间的递归式一般为。因此，出于方便，我们一般忽略递归式的边界条件，假设对很小的，为常量。
    • 去掉了很小时函数值的显式描述。原因在于，虽然改变的值会改变递归式的精确解，但改变幅度不会超过一个常数因子，因而函数的增长阶不会变化。

我们先忽略这些细节，稍后再确定这些细节对结果是否有较大影响。通常影响不大，但你需要知道什么时候会影响不大。这一方面可以依靠经验来判断，另一方面，一些定理也表明，对于很多刻画分治算法的递归式，这些细节不会影响其渐近界。

分治算法 - 用代入法求解递归式

未学习

分治算法 - 用递归树法求解递归式

未学习

分治算法 - 用主方法求解递归式

主方法为如下形式的递归式提供了一种”菜谱”式的求解方法：

• ，其中和是常数，是渐近正函数。

递归式描述的是这样一种算法的运行时间：它将规模为的问题分解为个子问题，每个子问题规模为，其中和都是正常数。个子问题递归地进行求解，每个花费时间。函数包含了问题分解和子问题解合并的代价。

主方法依赖于下面的定理:

• 令和是常数，是一个函数，是定义在非负整数上的递归式：，其中我们将b解释为或。那么有如下渐近界：
  • 1. 若对某个常数 有 ，则 。
  • 2. 若 ，则 。
  • 3. 若对某个常数 有 ，且对某个常数 和所有足够大的 有 ，则 。

对于三种情况的每一种，我们将函数 与函数 进行比较。直觉上，两个函数较大者决定了递归式的解。

• 若函数 更大，如情况1，则解为）。
• 若函数 更大，如情况3，则解为 。
• 若两个函数大小相当，如情况2，则乘上一个对数因子，解为 。

在第一种情况中，不是小于就够了，而是要多项式意义上的小于。也就是说，必须渐近小于要相差一个因子，其中是大于0的常数。

在第三种情况中，不是大于就够了，而是要多项式意义上的大于，而且还要满足“正则”条件。

动态规划

动态规划(dynamic programming)与分治方法相似，都是通过组合子问题的解来求解原问题。

动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治算法会做许多不必要的工作，它会反复地求解那些公共子子问题。而动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。

动态规划方法通常用来求解最优化问题(optimization problem)。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值（最小值或最大值）的解。我们称这样的解为问题的一个最优解(an optimal solution), 而不是最优解(the optimal solution) , 因为可能有多个解都达到最优值。

我们通常按如下4个步骤来设计一个动态规划算法：

• 1. 刻画一个最优解的结构特征。
• 2. 递归地定义最优解的值。
• 3. 计算最优解的值，通常采用自底向上的方法。
• 4. 利用计算出的信息构造一个最优解。

步骤1~3是动态规划算法求解问题的基础。如果我们仅仅需要一个最优解的值，而非解本身，可以忽略步骤4。如果确实要做步骤4,有时就需要在执行步骤3的过程中维护一些额外信息，以便用来构造一个最优解。

钢条切割

矩阵链乘法

动态规划原理

最长公共子序列

最优二叉搜索树

贪心算法

摊还分析