루프 불변 함수 작동

Question

루프 불변량에 대해 알고 싶습니다. 알고리즘 (주로 정렬 알고리즘)에는 루프 불변성이 있고 루프 불변성은 알고리즘의 정확성을 나타냅니다.

어떻게 작동합니까? 누군가 이걸 이해하는데 나를 도울 수 있습니까?

Answer 1

루프 불변 값 자체는 알고리즘의 정확성을 나타냅니다. 루프의 각 반복마다 참인 술어입니다. (대개 루프에 대해 술어가 실제로 불변임을 증명해야합니다.) 불변성은 루프의 다양한 속성 (아마도 정확함 포함)을 증명하는 데 사용될 수 있습니다. Wikipedia article Loop invariant에는 이것이 어떻게 작동 하는지를 보여주는 몇 가지 예가 있습니다. 더 많은 예제와 설명은 this thread을 참조하십시오.