알고리즘 분석
알고리즘의 효율성은 구현 전과 구현 후, 두 단계에서 평가할 수 있습니다.
사전 분석(A Priori Analysis) – 이론적인 분석 방식입니다. 프로세서 속도 등 하드웨어 관련 요소들은 모두 일정하다고 가정하고, 그 영향을 배제한 상태에서 알고리즘 자체의 효율성을 측정합니다.
사후 분석(A Posterior Analysis) – 실증적인 분석 방식입니다. 선택한 알고리즘을 프로그래밍 언어로 구현한 뒤 대상 컴퓨터에서 직접 실행하고, 실제 실행 시간과 소요된 메모리 공간 같은 통계를 수집하여 성능을 평가합니다.
알고리즘 분석은 알고리즘에 포함된 여러 연산의 실행 시간(running time)을 다루며, 한 연산의 실행 시간은 해당 연산당 실행되는 컴퓨터 명령어의 수로 정의할 수 있습니다.
알고리즘 복잡도
X를 하나의 알고리즘, N을 입력 데이터의 크기라고 가정하면, X의 효율성은 시간과 공간이라는 두 가지 핵심 요소에 의해 결정됩니다.
- 시간 요소(Time Factor) – 정렬 알고리즘의 비교 연산 횟수처럼 핵심 연산(key operation)이 몇 번 수행되는지 세어 측정합니다.
- 공간 요소(Space Factor) – 알고리즘이 실행 과정에서 필요로 하는 최대 메모리 공간을 세어 측정합니다.
알고리즘의 복잡도 f(N)은 입력 데이터의 크기 N에 대해 알고리즘의 실행 시간 및 저장 공간이 얼마나 필요한지를 나타내는 척도입니다.
공간 복잡도(Space Complexity)
알고리즘의 공간 복잡도는 알고리즘이 생명 주기(life cycle) 동안 필요로 하는 메모리 공간의 총량을 의미합니다. 알고리즘이 필요로 하는 공간은 다음 두 부분의 합으로 구성됩니다.
- 고정 부분(Fixed Part) – 단순 변수와 상수, 프로그램 코드 크기 등 문제의 크기와 무관하게 항상 필요한 저장 공간입니다.
- 가변 부분(Variable Part) – 재귀 호출 시의 스택 공간, 동적 메모리 할당처럼 문제의 크기에 비례하여 달라지는 저장 공간입니다.
따라서 임의의 알고리즘 p의 공간 복잡도는 다음과 같이 표현됩니다.
S(p) = A + Sp(I)
여기서 A는 고정 부분, S(I)는 입력 인스턴스의 특성 I에 따라 달라지는 가변 부분입니다.
예제 알고리즘
SUM(P, Q) Step 1 - START Step 2 - R ← P + Q + 10 Step 3 - Stop
위 예제에는 세 개의 변수(P, Q, R)와 하나의 상수가 사용되었으므로 S(p) = 1 + 3이 됩니다. 실제 메모리 사용량은 변수와 상수의 데이터 타입 크기에 따라 곱해져 최종적으로 계산됩니다.
시간 복잡도(Time Complexity)
알고리즘의 시간 복잡도는 알고리즘이 완료될 때까지 실행되는 데 필요한 시간의 양을 나타냅니다. 시간 요구량은 수치 함수 t(N)로 정의할 수 있으며, 각 단계가 일정한 시간(constant time)을 가진다는 조건에서 t(N)은 실행 단계의 수로 측정됩니다.
예를 들어, n비트 정수 두 개를 더하는 경우 N번의 단계가 필요합니다. 따라서 총 계산 시간은 t(N) = c × n으로 표현되며, 여기서 c는 두 비트를 더하는 데 소요되는 시간입니다. 이 예제에서 확인할 수 있듯이, 입력 크기가 증가함에 따라 t(N)은 선형적으로(linearly) 증가합니다.