알고리즘 평가 기준

알고리즘을 평가하는 기준

* 시간 : 최대한 적은 시간이 걸려야한다.

* 공간 : 적은 용량의 메모리를 사용하여야한다.

두 기준은 서로 상충하는 경우가 많다

요즘은 메모리가 대부분 충분하기 때문에 시간을 우선시한다. 

알고리즘 수행 시간 측정

반복문이 수행 시간에 큰 부분을 차지한다.

 - 선형 시간 알고리즘 : 좋음

 - 선형 이하 시간 알고리즘 : 입력의 크기가 커지는 것보다 수행 시간이 느리게 증강하는 알고리즘

 - 다항 시간 알고리즘 : 변수 N과 N2, N의 거듭제곱들의 선형 결합으로 이루어진 식

 - 지수 시간: 가장 큰 수행 시간 중 하나

 - 소인수 분해의 수행시간

입력의 값이 커질수록 필요한 메모리 공간도 증가. 입력이 차지하는 비트 수에 따라 수행 시간이 증가

시간 복잡도

알고리즘 수행 시간의 기준. 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것이다

완전한 속도의 기준은 아니다. 입력의 크기가 매우 작을 경우 시간 복잡도가 높은 알로리즘이 더 빠를 수 있다.

출처 및 참고

- 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1, 구종만 지음

점근적인 시간 표기 : O표기

모든 기본 연산을 셀 수 없으므로, 큰 영향을 주지 않는 상수 부분은 무시하고 반복문의 반복 수만 고려하게 된다.

O 표기법 : 주어진 함수에서 가장 빨리 증가하는 항만을 남긴 채 나머지는 다 버리는 표기법

문제의 특성

계산 복잡도 이론에서 다항 시간 알고리즘이 존재하는 문제를 P문제라고 한다.

NP 문제 : 답이 주어졌을 때 정답인지 다항 시간 내에 확인할 수 있는 문제

NP-난해 문제 : NP 문제 이상으로 어려운 문제, 해당 문제를 다항 시간에 풀 수 있으면 모든 NP문제를 다항 시간에 풀 수 있다.

NP-완비 문제 : NP난해 문제이면서 NP인 문제들