알고리즘 분석 기준과 유형

알고리즘을 분석하기 위해서는 기준이 필요하다. 필요한 기준은 다음과 같다.

• 정확성 : 적당한 입력에 대해서 유한 시간에 올바른 답을 산출하는가?
• 작업량 : 전체 알고리즘에서 가장 중요한 연산들만으로 작업량을 측정
• 단순성
• 기억장소 사용량 분석
• 최적성 : 최적이란 가장 '잘 알려진'이 아니라 '가장 좋은'의 의미이다.

 

보통 알고리즘을 분석할 때 시간복잡도(Time complexity)와 공간 복잡도의 관점으로 평가한다. 시간 복잡도는 계산 문제의 소요시간등을 측정하고, 공간 복잡도는 메모리의 사용량을 기준으로 평가한다.

 

또한, 실제 코드를 작성한 후 실행하여 시간을 측정하는 경험적 분석(emprical analysis)와 알고리즘 자체로 수학적인 분석(mathematical analysis)이 있다.

 

 

 

알고리즘의 유형

 

알고리즘 분석 결과를 입력되는 자료의 수 N에 대해 수행되는 시간을 함수 관계로 표시한다. 종류는 다음과 같다.

 

O(1)

입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘. 항상 실행 시간이 상수로 변하지 않음

 

O(log N)

주로 커다란 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형으로 N이 증가함에 따라 실행 시간이 조금씩 늘어난다. 이 유형의 알고리즘은 바람직한 실행 시간을 갖는다. 성능 좋은 검색 알고리즘은 대부분 이 유형을 나타낸다.

 

O(N)

입력 자료에 따라 비례하여 실행 시간이 증가하는 경우이다. 즉, N이 두 배로 늘어나면 실행 시간도 두 배로 늘어난다.

 

O(N log N)

커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고, 나중에 다시 그것들을 하나로 모으는 경우에 나타난다. N이 두배로 늘어나면 실행 시간은 두 배보다 약간 더 많이 늘어난다.

 

O(n^2)

이중 루프 내에서 입력 자료를 처리하는 경우에 나타난다. N 값이 크면 실행 시간을 감당하지 못할 정도로 커지게 된다. 따라서 많은 양의 자료를 처리할 경우 부적절하다. 하지만 N의 크기가 작을 때에는 N log N 보다 실행 시간이 작을 수 있다.

 

O(n^3)

입력 자료를 삼중 루프 내에서 처리하는 경우에 나타난다. N이 두 배로 늘어난다면 실행시간은 여덟배로 늘어난다.

 

O(2^n)

입력 자료의 수가 늘어남에 따라 급격하게 실행 시간이 늘어난다. 가끔식 알고리즘을 처음 개발할 때 나나탈 수 있는 알고리즘이다. N이 두 배로 늘어난다면 실행 시간은 제곱으로 늘어난다.

 

 

[참고] 위키백과