알고리즘의 정확성 평가

Loop invariant 를 통해 체크

루프 중 불변의 부분을 찾는 것으로 정확도를 증명 Loop invariant란 루프를 돌 동안 유지 되어야 하는 statement이다.

Loop invariant를 증명 세가지 성질

1) 초기 조건 (initialization)

루프에 처음 들어갈때 변수의 변화 및 조건의 변화가 맞는지 판단해서, 루프에 정확하게 들어가는 지 확인

2) 유지 조건 (Maintenance)

루프가 시작하기 전부터 다음 루프로 넘어가기 전까지 만족해야 되는 조건, 이 조건이 알고리즘의 목적에 부합하는지를 판단

3) 종료 조건 (Termination)

루프가 끝났을 때, 우리는 사용가능하고 유용한 결과를 얻어야 하며, 이것이 문제해결(알고리즘의 목표)에 도움이 되는 겨로가가 나오는지 확인한다.

시간 복잡도 표기

세타(Theta) 표기법 - tight bound

빅 세타는 빅 오와 빅 오메가의 공통부분, 최소와 최악의 중간이 평균적인 복잡도, 정확함

빅-오(Big-Oh) 표기법 - upper bound

Worst case를 나타내기 때문에 시간복잡도를 논할 때 일반적으로 많이 사용

빅-오메가(Big-Omega) 표기법 - lower bound

빅 오메가는 빅오와는 반대되는 개념. 대개 최선의 경우

빅오와 스몰오의 차이

빅오는 같은 경우를 포함하고 스몰오는 같은 경우를 포함하지 않는다.

알고리즘 분석 기준

정확성 : 올바른 입력에 대해 유한 시간 내에 옳은 답을 내는 것을 의미한다.

수행량 : 알고리즘을 수행하는데 걸리는 수행 횟수를 나타내는데, 최상의 경우, 최악의 경우, 평균의 경우로 나타낼 수 있다.

기억장소 사용량 : 알고리즘 수행 시 필요한 컴퓨터의 기억 공간의 사용량을 의미한다.

단순성/명확성 : 알고리즘의 작성이 쉽고 간결하여 해독성이 높아야 한다는 것을 말한다.

최적성 : 어떤 알고리즘이 최적이다 라고 하는 것은 그 알고리즘보다 더 적은 중요 연산을 수행하는 알고리즘이 없다는 것을 의미한다.

최적 알고리즘을 찾기 위한 과정

  1. 고안한 알고리즘의 최악의 경우에 필요한 작업량 W(n)을 구한다.

  2. 최소 작업량 F(n) 필요를 증명

  3. W(n) = F(n) 을 만족한다면 최적 알고리즘