Python数据结构 算法证明

为了宣称一个算法是高效的，我们需要一些数学工具作为证明。这些工具可以帮助我们对算法的性能和准确性提供一个数学上令人满意的解释。下面是一些数学工具的清单，它们可以用来证明一种算法比另一种算法更有效。

• 直接证明– 它是通过使用直接计算来直接验证声明。例如，两个偶数的总和总是一个偶数。在这种情况下，只需将你所调查的两个数字相加，并验证其结果为偶数。

• 归纳证明– 这里我们从真理的一个具体实例开始，然后将其归纳为真理的所有可能值。其方法是先取一个已验证的真理案例，然后证明在相同的给定条件下，它对下一个案例也是真的。例如，所有形式为2n-1的正数都是奇数。我们对某一数值的n进行证明，然后对下一个数值的n进行证明。这样，通过归纳证明，这句话就被确定为普遍正确。

• 矛盾证明– 这种证明是基于这样的条件：如果不是A意味着不是B，那么A就意味着B。因为如果n的平方不是偶数，那么n就不是偶数。

• 穷举证明– 这类似于直接证明，但它是通过单独访问每个案例并证明每个案例而建立的。这种证明的一个例子是四色定理。