Algorithm Justifications

为了使算法的效率变得有效，我们需要一些数学工具作为证据。 这些工具帮助我们提供关于算法的性能和准确性的数学上令人满意的解释。 下面列出了一些可用于证明一种算法优于另一种算法的数学工具。

• Direct Proof:

  它是使用直接计算直接验证声明。 例如，两个偶数之和总是偶数。 在这种情况下，只需添加您正在调查的两个数字，并将结果验证为均匀。

• Proof by induction:

  在这里，我们从一个特定的事实实例开始，然后将其推广到所有可能的值，这些值是真理的一部分。 该方法是采用经过验证的事实的案例，然后证明对于相同的给定条件下一个案例也是如此。 例如，形式2n-1的所有正数都是奇数。 我们证明它是n的某个值，然后证明它是n的下一个值。 这通过归纳证明确定了声明。

• Proof by contraposition:

  该证明基于条件如果不是A暗示不是B则A暗示B.一个简单的例子是如果n的平方是偶数则n必须是偶数。 因为如果n上的平方不均匀则n不均匀。

• Proof by exhaustion:

  这类似于直接证明，但它是通过分别访问每个案例并证明其中的每一个来建立的。 这种证明的一个例子是四色定理。