The RAM Model of Computation

개요

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

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

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