The RAM Model of Computation

개요

기계와 상관없이 독립적으로 작동하는 알고리즘의 설계는 RAM(Random Access Machine)이라고 불리는 가상의 컴퓨터에 의존한다. 이때 해당 컴퓨터의 특징은 아래와 같다.

• 각각의 단순 연산(+, *, –, =, if, call)은 정확히 한 시간 단계(time step)를 소요한다.
• 반복문과 서브루틴은 단순 연산으로 간주되지 않는다.
• 각 메모리 접근은 정확히 한 시간 단계(time step)를 소요한다.

RAM 모델에서 실행 시간은 주어진 문제 인스턴스에서 알고리즘이 수행하는 단계 수를 통해 측정한다. 이때 RAM이 초당 일정한 수의 단계를 수행한다고 가정한다면, 이 연산 계수는 실제 실행 시간으로 자연스럽게 변환된다. RAM은 컴퓨터가 수행하는 방식을 단순화한 모델이다. 이는 너무나 단순화한 나머지 실제로 컴퓨터가 동작하는 방식과는 차이가 있지만, RAM은 실제 컴퓨터에서 알고리즘이 어떻게 성능을 낼지를 이해하는 데 훌륭한 모델이다.

Best/Worst/Average-Case Complexity

RAM 모델을 사용하면 주어진 입력 인스턴스에 대해 알고리즘을 실행하여 해당 알고리즘이 수행하는 단계의 수를 셀 수 있다. 그러나 일반적으로 어떤 알고리즘이 좋은지 나쁜지를 판단하기 위해서는, 가능한 모든 인스턴스에 대해 그것이 어떻게 동작하는지를 알아야 한다.

최선, 최악, 평균 경우 복잡도(Best/Worst/Average-Case Complexity)의 개념을 이해하기 위해서 해당 알고리즘에 입력될 수 있는 가능한 모든 데이터 인스턴스에 대해 알고리즘을 실행한다고 가정하자. 예를 들어 정렬 문제의 경우, 가능한 입력 인스턴스 집합은 모든 가능한 n개의 키의 배열이다. 이때 각 입력 인스턴스는 figure 1에 나타난 좌표평면 위의 한 점으로 나타내어 진다. 해당 좌표평면에서 x축은 입력 문제의 인스턴스 크기를, y축은 해당 인스턴스에서 알고리즘이 수행한 단계의 수를 나타낸다. 이때 우리는 해당 좌표평면에서 세 가지 흥미로운 함수를 정의할 수 있다.

1. Worst-Case Complexity는 크기 n의 어떤 인스턴스에 대하여 수행된 단계 수의 최댓값으로 정의되는 함수이다. 이는 평면에서 가장 높은 점을 지나는 곡선에 해당된다.
2. Best-Case Complexity는 크기 n의 어떤 인스턴스에 대하여 수행된 단계 수의 최솟값으로 정의되는 함수이다. 이는 평면에서 가장 낮은 점을 지나는 곡선에 해당된다.
3. Worst-Case Complexity는 크기 n의 모든 인스턴스에 대해 실행된 단계 수의 평균으로 정의되는 함수이다.

일반적으로는 이 세가지 측정치 중 Worst-Case Complexity가 가장 유용하다.