자료구조 및 실습 - [1] 알고리즘 분석 (2)

지난 포스팅에서는 알고리즘 분석에 필요한 기본적인 것들을 적었다. 

의사 코드를 활용하여 알고리즘을 표현하기도 하는데, 전에 배웠듯이 사용하는 하드웨어와 소프트웨어에 관계없이 실행시간을 추정해야 한다. 

이때 임의접근기계 모델(Random Access Machine, RAM)을 사용하는데, 

• 하나의 중앙처리장치(CPU)
• 무제한의 메모리셀

을 사용하고, 메모리 셀들은 순번으로 나열되며 어떤 셀에 대한 접근이라도 동일한 시간 단위(상수)가 소요된다고 가정한다.

또한 원시 작업(Primitive Operations)의 최대 개수를 입력크기의 함수 형태로 결정할 수 있는데, 원시 작업이란 알고리즘에 의해 수행되는 기본적인 계산을 의미한다. 

 

  예를 들어

• 산술식/논리식의 평가 (EXP)
• 변수에 특정값을 치환 (ASS)
• 배열원소 접근 (IND)
• 메쏘드 호출 (CAL)
• 메쏘드로부터 반환 (RET)

등이 있다. 원시 작업은 임의 접근 기계 모델에서 수행 시 상수 시간이 소요된다고 가정한다.

 

원시작업 수를 센 의사코드

우리는 원시작업의 최대 개수를 활용하여 실행시간을 추정할 수 있다.

위의 arrayMax는 최악의 경우 7n-2 개의 원시작업을 실행하는데, a = 가장 빠른 원시 작업 실행에 걸리는 시간 / b = 가장 느린 원시작업 실행에 걸리는 시간이라고 정의하고 T(n) = arrayMax의 최악인 경우의 시간이라고 놓으면 다음 식이 성립한다.

$$ a(7n-2) <= T(n) <= b(7n-2) $$

즉, 실행시간 T(n)은 두 개의 선형 함수 사이에 놓이게 되고, 하드웨어나 소프트웨어 환경을 변경하면 T(n)의 상수 배수만큼의 영향을 주지만, T(n)의 증가율은 변하지 않는다. 따라서 선형의 증가율을 나타내는 실행시간 T(n)은 arrayMax의 고유한 속성이다.

 

 

---

우리는 점근분석(asymptotic analysis)을 함으로써 Big-oh 표기법에 의한 실행시간을 구할 수 있다. 점근 분석을 수행하기 위해서는 두 가지 단계를 거친다.

• 최악의 원시작업 실행 횟수를 입력 크기의 함수로서 구한다.
• 이 함수를 big-oh 표기법으로 나타낸다.

위와 같이 7n-2개의 원시작업을 실행한다면, "알고리즘이 O(n)시간에 수행된다."라고 말한다. (상수 계수와 낮은 차수의 항들은 결국 탈락되므로 원시 작업 수를 계산할 때부터 이들을 무시 가능)

반복문, 연속 문, 조건문 등은 자주 보면 실행시간을 빠르게 눈치챌 수 있다. 

 

전형적인 증가함수들의 Plot을 보자.

전형적인 증가 함수들의 플롯

우리는 $$ 2^n, n^3, n^2 $$ 등의 증가율을 가지는 알고리즘을 $$ nlogn $$ 혹은 그 이하의 증가율을 가지도록 만들기를 원한다!