Python - 算法理由



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

  • 直接证明 − 通过使用直接计算对声明的直接验证。例如,两个偶数之和始终为偶数。在这种情况下,只需将您正在调查的两个数字相加,并验证结果为偶数。
  • 归纳证明 − 在这里,我们从真值的特定实例开始,然后将其推广到作为真值一部分的所有可能值。方法是采用一个已验证的 true 案例,然后证明对于相同的给定条件,下一个案例也是正确的。例如,2n-1 形式的所有正数都是奇数。我们证明它为 n 的某个值,然后为下一个值 n 证明它。这通过归纳证明将陈述确定为普遍正确。
  • 反立证明 − 此证明基于条件 If Not A implies Not B then A implies B。一个简单的例子是,如果 n 的平方是偶数,那么 n 必须是偶数。因为如果 n 上的平方不均匀,那么 n 就不均匀。
  • 穷举证明 - 这类似于直接证明,但它是通过单独访问每个案例并证明每个案例来确定的。这种证明的一个例子是四色定理。