Algorithm(14)
-
[알고리즘 문제해결 전략]5장. 알고리즘의 정당성 증명
Preview 알고리즘의 정확한 증명을 위해서 수학적인 기법을 동원하여 증명한다. 1. 귀납법2. 귀류법3. 그외 다른 기술들 1. 귀납법 반복적인 구조를 갖는 명제들을 증명하는데 유용하게 사용된다. 단계를 나눠 보자 1단계 증명하고 싶은 사실을 여러 단계로 나누자. 2단계 첫단계의 내용이 성립함을 보이자. 3단계 한 단계에서 증명하고 싶은 내용이 성립한다는 가정하에 그 다음 단계도 성립함을 보이자. 반복문을 통해 귀납법의 정당성을 고려해 보자 1단계 반복문 진입시에 불변식이 성립함을 보인다. 2단계 반복문 내용이 불변식을 깨뜨리지 않음을 보인다. 다르게 말하면, 반복문 내용이 시작할때 불변식이 성립했다면 내용이 끝날 때도 불변식이 항상 성립함을 보인다. 3단계 반복문 종료시에 불변식이 성립하면 항상 우..
2018.12.27 -
[알고리즘 문제해결 전략]4장. 알고리즘의 시간 복잡도 분석
Preview알고리즘의 시간 복잡도는 알고리즘의 수행 시간을 반복문이 수행되는 횟수로 측정한다 --> 주로 입력되는 크기에 대한 함수로 표현된다. 1. 선형 시간 알고리즘2. 선형 이하 시간 알고리즘3. 지수시간 알고리즘4. 시간 복잡도5. 수행시간 어림 짐작하기6. 계산 복잡도 클래스 1. 선형 시간 알고리즘 입력의 크기에 대비해 걸리는 시간을 그래프로 그려보면 직선이 되는 알고리즘 EX>매달 N개의 측정치가 주어질 때, 매달 M달간의 평균을 구해라. ⅰ) 마구잡이로 풀어보기 1234567891011vector GetAvg(const vector& A, int M){ vector ret; int N = A.size(); for(int i = M - 1; i 5. 수행시간 어림짐작하기 입력의 크기를 시간..
2018.12.27