Python Data Structure 简明教程

Python - Algorithm Justifications

为了对算法的效率做出宣称，我们需要一些数学工具作为证明。这些工具帮助我们对算法的性能和准确性提供了数学上令人满意的解释。以下是可用于证明一种算法优于另一种算法的一些数学工具列表。

  1. Direct Proof − 这是通过使用直接计算对语句的直接验证。例如，两个偶数的和始终是偶数。在这种情况下，只需将你要调查的两个数字相加，并将结果验证为偶数即可。

  2. Proof by induction − 在这里，我们从一个真理的特定实例开始，然后将其概括到属于该真理的所有可能的值。其方法是取一个经过验证的真值案例，然后证明在相同的给定条件下，对于下一个案例也是成立的。例如，所有形式为 2n-1 的正数都是奇数。我们为 n 的某个特定值证明它，然后为 n 的下一个值证明它。这通过归纳证明将陈述确定为通常是正确的。

  3. Proof by contraposition − 该证明基于以下条件：如果不 A，则意味着不 B 那么 A 意味着 B。一个简单的示例是，如果 n 的平方是偶数，则 n 必定是偶数。因为如果 n 的平方不是偶数，则 n 就不是偶数。

  4. Proof by exhaustion − 这与直接证明类似，但通过分别查看每个案例并证明每个案例来建立的。这种证明的一个示例是四色定理。