Python-data-structure-python-algorithm-justifications

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

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

• 直接証明： +直接計算を使用したステートメントの直接検証です。 たとえば、2つの偶数の合計は常に偶数です。 この場合、調査中の2つの数値を追加して、結果が偶数であることを確認します。
• 帰納法による証明： +ここでは、真実の特定のインスタンスから始めて、真実の一部であるすべての可能な値にそれを一般化します。 アプローチは、検証された真実のケースを採用し、同じ与えられた条件の次のケースにも当てはまることを証明することです。 たとえば、2n-1形式のすべての正数は奇数です。 nの特定の値について証明し、次にnの次の値について証明します。 これにより、誘導の証拠により、ステートメントが一般的に正しいことが確立されます。
• 対比による証明： +この証明は、条件Aに基づいてNot AがNot Bを意味する場合、AはBを意味します。 簡単な例は、nの2乗が偶数の場合、nは偶数でなければなりません。 nの正方形が偶数でない場合、nは偶数ではないからです。
• 消耗による証明： +これは直接証明に似ていますが、各ケースを個別に訪問し、それぞれを証明することで確立されます。 そのような証明の例は、4色の定理です。