[ Open Data Structures ] - The model of Computation

The Model of Computation

자료구조의 Operation의 이론적인 Running time을 정확하게 분석하기 위해서 우리는 Mathematical model of computation이 필요하다. 이를 위해서, w-bit word-RAM 모델을 사용할 것이다.

RAM은 'Random Access Machine'의 약자이다. 이 모델에서는, w-bit word를 저장하고 cell로 구성되어 있는 random access memory에 접근할 수 있다. 이는 곧 예를 들어서, Memory cell은 어떤 정수의 집합 {0, .. 2^w - 1}을 나타낼 수 있다는 것이다. 

'Memory cell is an electronic circuit that stores one bit of information and it must be set to logic 1 (high voltage)and reset to store a logic 0 (low voltage).'

Word-RAM 모델에선 word에 대한 간단한 operation이 상수 시간이 걸린다. 이 '간단한 operation'에는 산술적인 연산(+,-,*,/,%)과 비교연산(<,>,<=,>=,=), 그리고 bitwise boolean operation(bitwise-AND, OR, 그리고 exclusive-OR)이 포함된다.

 A bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits.

어떤 Cell이든 상수 시간 내에 읽고(Read) 쓸(Write) 수 있다. 컴퓨터의 메모리는 'Memory Management System'에 의해서 우리가 원하는 대로 할당/해제할 수 있다. 크기 k에 해당하는 블록(Block)을 할당하는 것은 O(k)시간이 걸리며 새롭게 할당된 메모리 블록의 Reference(혹은 Pointer)를 반환한다. 이 Reference는 한 Word에 표현할 수 있을 만큼 충분하게 작다.

word의 크기 w는 이 모델의 매우 중요한 parameter다. w에 대해서 할 유일한 가정은 n이 어떤 자료구조에 저장된 원소(Element, 일단은 자료나 정보)의 개수일 때, w의 최소값이

에 해당한다는 것이다. 이건 상당히 적절한 가정인데, 그렇지 않으면 word가 자료구조 내의 원소를 셀 수 있을 만큼 충분히 크지 않기 때문이다.

공간(Space)역시 word로 측정하기 때문에 자료구조의 공간을 이야기 할 때는 자료구조에 의해 사용되고 있는 메모리의 word의 수를 이르는 것이다. 일단은 모든 자료구조의 Element 'T'를 Generic하게 구현하기 때문에 T가 메모리의 한 word를 점유한다고 가정한다.

이 w-bit word RAM 모델은 w=32, w=64일 때, 현대 Desktop Computer에 근접한다. 

Correctness, Time Complexity, and Space Complexity

자료구조의 성능을 공부함에 있어서 다음 세 가지의 중요한 요소를 기억해야 한다.

1. Correctness : 자료구조는 Interface를 정확히 구현해야 한다.

2. Time Complexity : 각 Operation의 Running time은 가능한 최소가 되어야 한다.

3. Space Complexity : 자료구조는 가능한 적은 양의 메모리를 사용해야 한다.

또, 자료구조의 Running time을 공부할 때, 서로 다른 세 가지의 Running time guarantees를 마주치게 된다.

1. Worst-case Running times 

- 가장 강력한 Running time guarantees다. 만일 어떤 자료구조의 operation들이 worst-case running time f(n)을 가진다면, 어떤 작업도 f(n)이상 걸리지 않는다.

2. Amortised Running times

- 만약 어떤 자료구조의 한 operation의 Amortised running time이 f(n)이라면 일반적으로 operation들이 최대 f(n)의 running time을 가진다는 뜻이다. 더 엄밀하게는, 만약 어떤 자료구조의 한 operation이 Amortised running time이 f(n)이라면 일련의 m번의 operation들은 최대 m*f(n)의 running time을 가진다는 뜻이다. 일련의 operation의 나열 속에 특정한 operation이 f(n) 이상의 running time을 가질 수는 있지만 평균적으로는 전체 operation의 running time은 최대 f(n)이다.

3. Expected Running times

- 만약 어떤 자료구조의 한 operation의 Expected running time이 f(n)이라면 이는 실질적인 running time은 랜덤 변수이며 이 랜덤 변수의 기댓값(Expected Value)이 최대 f(n)이라는 뜻이다. 여기서의 Randomisation(랜덤화)은 자료구조에 의해 결정되는 무작위 선택에 관한 것이다.

각각의 경우를 빠르게 이해하기 위해서는 다음 예제를 보는 것이 도움이 된다. 집을 구매할 때 드는 비용을 고려해본다.

Worst-Case versus Amortised Cost

120,000달러짜리 집이 있다고 가정한다. 이 집을 사기 위해서 월 1,200달러를 지불하는 십 년(120개월)만기 모기지를 선택할 수 있다. 이 경우 최악의 경우에 모기지를 갚는 것에 대해서 월 1,200달러를 지불하게 된다. (Worst-Case)

이번엔 운이 좋아서 충분한 현금이 있어서 120,000달러를 한 번에 지불해버리고 집을 완전히 사버리는 경우가 있을 수 있다. 이 경우엔 10년에 걸쳐서 지불하는 월 비용은 120,000달러 / 120개월 = 1,000달러다. (Amorised Case)

모기지를 선택하지 않고 한 번에 지불하는 경우가 훨씬 저렴하다.

Worst-Case versus Expected Cost

다음은 이 120,000달러 집에 들 화재보험을 생각해본다. 수 백, 수 천 개의 경우를 분석하여 보험회사는이러한 집에 화재로 인한 예상피해액을 월 10달러로 책정했다. 이는 굉장히 낮은 숫자인데 대부분의 집에서 화재가 발생하지 않으며 발생하더라도 담뱃불에 의한 작은 화재 정도이고 아주 극소수의 집만이 홀라당 불타버리기 때문에 책정된 금액이다. 이 금액을 바탕으로 보험사는 우리집(120,000달러짜리)에 월 15달러의 보험금을 책정한다.

이제 결정의 시간이다. 최악의 경우인 월 15달러를 보험사에 낼 것인지, 아니면 화재로 인한 예상피해액인 10달러에 도박을 걸 것인지를 말이다. 확실히, 월 10달러를 지출하는 것이 적은 기댓값을 가지기는 하지만 집이 홀라당 불타버릴 경우 못해도 120,000달러의 비용을 떠앉게 된다는 사실을 받아들여야만 한다.

이 예제들은 worst-case가 아닌 amortised나 expected running time에 집착하는가에 대한 통찰을 하게 해준다. 가끔씩 worst-case에 비해서 낮은 amortised/expected running time을 얻는 것이 가능하다. 최소한 amortised나 expected running time을 고집하다가 보면 더 단순한 자료구조를 얻는 일이 굉장히 흔하다고는 할 수 있다.