算法设计技术

以下是几种流行的设计方法的列表：

1.分而治之：这是一种自上而下的方法。遵循分而治之技术的算法包括三个步骤：

• 将原始问题分为一组子问题。
• 递归地分别解决每个子问题。
• 将子问题（顶层）的解决方案组合为整个原始问题的解决方案。

2.贪婪技术：贪婪方法用于解决优化问题。最优化问题是给我们提供一组输入值, 这些输入值需要最大化或最小化（称为目标）, 即一些约束或条件。

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

3.动态编程：动态编程是一种自下而上的方法, 我们先解决所有可能的小问题, 然后将它们组合起来以解决更大的问题。

当复制子问题的数量成倍增加时, 这特别有用。动态编程通常与优化问题有关。

4.分支和边界：在分支和边界算法中, 无法约束的给定子问题必须分成至少两个新的受限子问题。分支和边界算法是非凸问题中全局优化的方法。分支和边界算法可能很慢, 但是在最坏的情况下, 它们需要的工作量随问题的大小呈指数增长, 但是在某些情况下, 我们很幸运, 而且方法的工作量也要少得多。

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

6.回溯算法：回溯算法会尝试每种可能性, 直到找到正确的可能性为止。这是一组可能解决方案的深度优先搜索。在搜索过程中, 如果替代方法不起作用, 则返回到选择点, 即提供不同替代方法的位置, 然后尝试下一个替代方法。

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

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

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

循环不变式

这是一种证明技术。我们使用循环不变式来帮助我们理解为什么算法正确。为了证明关于循环的陈述S是正确的, 请定义关于一系列较小的陈述S0 S1 …. Sk的S, 其中,

• 循环开始之前的最初要求是正确的。
• 如果Si-1在迭代i开始之前为真, 则可以证明Si在迭代i结束之后为真。
• 最后的陈述Sk表示我们希望证明其为正确的陈述S。