728x90 loop1 Loop Invariant 루프 불변성 (feat. Insertion Sort) 루프 불변성은 알고리즘이 올바른지 증명하는데 사용된다. Initialization(초기화) : 첫 번째 루프 반복 전에 루프 불변량이 유지된다는 것을 보여준다 j=2의 경우 해당배열(하위배열)은 A[1] 단일 element로 정렬되어있다고 볼 수 있다. Maintenance(유지) : 각 반복이 루프 불변성을 유지한다는 것을 보여준다. A[1.. j] 하위배열이 정렬되어있음 Termination(종료) : 루프가 종료되면 불변량은 알고리즘이 정확하다는 것을 보여주는 데 도움이 되는 유용한 속성을 제공한다. 루프 종료 조건은 j > A.length (=n), j = n-1 하위 배열 A[1..n]가 전체 배열이라는 것을 관찰하면 전체 배열이 정렬되었다고 결론을 내린다. 따라서, 알고리즘은 정확하다. loo.. 2022. 11. 8. 이전 1 다음 728x90
