Python-アルゴリズムの正当化

アルゴリズムが効率的であると主張するためには、証拠としていくつかの数学的ツールが必要です。これらのツールは、アルゴリズムのパフォーマンスと精度について数学的に満足のいく説明を提供するのに役立ちます。以下は、あるアルゴリズムを別のアルゴリズムよりも正当化するために使用できるいくつかの数学ツールのリストです。

• Direct Proof:

  直接計算によるステートメントの直接検証です。たとえば、2つの偶数の合計は常に偶数です。この場合、調査している2つの数値を加算して、結果が偶数であることを確認します。

• Proof by induction:

  ここでは、真理の特定のインスタンスから始めて、それを真理の一部であるすべての可能な値に一般化します。アプローチは、検証された真実のケースを取り、それが同じ与えられた条件の次のケースにも当てはまることを証明することです。たとえば、2n-1の形式のすべての正の数は奇数です。nの特定の値に対してそれを証明し、次にnの次の値に対してそれを証明します。これは、帰納法の証明によって一般的に真実であるとしてステートメントを確立します。

• Proof by contraposition:

  この証明は、NotAがNotBを意味する場合、AはBを意味するという条件に基づいています。簡単な例は、nの2乗が偶数の場合、nは偶数でなければならないというものです。nの正方形が偶数でない場合、nは偶数ではないためです。

• Proof by exhaustion:

  これは直接証明に似ていますが、それぞれのケースを個別に訪問し、それぞれを証明することによって確立されます。そのような証明の例は、四色定理です。