Python-알고리즘 정당화

알고리즘이 효율적이라는 주장을하기 위해서는 증거로 수학적 도구가 필요합니다. 이러한 도구는 알고리즘의 성능과 정확성에 대해 수학적으로 만족스러운 설명을 제공하는 데 도움이됩니다. 다음은 한 알고리즘을 다른 알고리즘보다 정당화하는 데 사용할 수있는 몇 가지 수학적 도구 목록입니다.

• Direct Proof:

  직접 계산을 사용하여 진술을 직접 확인합니다. 예를 들어 두 개의 짝수의 합은 항상 짝수입니다. 이 경우 조사중인 두 숫자를 추가하고 결과를 짝수로 확인하십시오.

• Proof by induction:

  여기서 우리는 진리의 특정 사례로 시작하여 진리의 일부인 가능한 모든 값으로 일반화합니다. 접근 방식은 확인 된 진실의 경우를 취한 다음 동일한 주어진 조건에 대해 다음 사례에 대해서도 참임을 증명하는 것입니다. 예를 들어 2n-1 형식의 모든 양수는 홀수입니다. 우리는 n의 특정 값에 대해 증명하고 다음 n 값에 대해 증명합니다. 이것은 귀납 증명에 의해 진술이 일반적으로 사실임을 입증합니다.

• Proof by contraposition:

  이 증명은 If Not A가 Not B를 의미하고 A는 B를 의미합니다. 간단한 예는 n의 제곱이 짝수이면 n이 짝수 여야한다는 것입니다. n의 제곱이 짝수가 아니면 n은 짝수가 아니기 때문입니다.

• Proof by exhaustion:

  이는 직접 증명과 유사하지만 각 사례를 개별적으로 방문하여 각각을 증명함으로써 설정됩니다. 그러한 증명의 예는 네 가지 색 정리입니다.