算法设计技术

以下是几种常用的设计方法

1. 分治法：这是一种自顶向下的方法。 遵循分治技术的算法涉及三个步骤

• 将原始问题分解为一组子问题。
• 递归地单独解决每个子问题。
• 将子问题的解（顶级）组合成整个原始问题的解。

2. 贪心技术：贪心方法用于解决优化问题。 优化问题是指给定一组输入值，需要将其最大化或最小化（称为目标），即某些约束或条件。

• 贪心算法总是在当前时刻做出看起来最好的选择（贪心标准），以优化给定的目标。
• 贪心算法并不总是保证最优解，但通常会产生一个与最优解非常接近的解。

3. 动态规划：动态规划是一种自底向上的方法，我们解决所有可能的小问题，然后将它们组合起来以获得更大问题的解决方案。

当复制子问题的数量呈指数增长时，这特别有用。 动态规划通常与**优化问题**相关。

4. 分支定界：在分支定界算法中，给定的子问题，如果不能被限定，必须被分解为至少两个新的受限子问题。 分支定界算法是非凸问题中的全局优化方法。 分支定界算法可能很慢，但在最坏的情况下，它们所需的计算量会随着问题规模呈指数增长，但在某些情况下，我们很幸运，该方法所需的计算量要少得多。

5. 随机算法：随机算法被定义为允许访问一组独立的、无偏的随机位的算法，然后允许使用这些随机位来影响其计算。

6. 回溯算法：回溯算法尝试每一种可能性，直到找到正确的可能性。 它是可能解决方案集合的深度优先搜索。 在搜索期间，如果一个备选方案不起作用，则回溯到选择点，即呈现不同备选方案的位置，并尝试下一个备选方案。

7. 随机算法：随机算法在计算过程中至少使用一次随机数来做出决定。

示例 1：在快速排序中，使用随机数选择一个枢轴。

示例 2：尝试通过选择一个随机数作为可能的除数来分解一个大数。

循环不变量

这是一种证明技术。 我们使用循环不变量来帮助我们理解算法为何正确。 为了证明关于循环的语句 S 是正确的，定义关于一系列较小语句 S₀ S₁....S_k，其中，

• 在循环开始之前，初始声明 so 为真。
• 如果 S_i-1 在迭代 i 开始之前为真，那么可以证明在迭代 i 结束后 S_i 将为真。
• 最终语句 S_k 意味着我们希望证明为真的语句 S 是真的。