1.2 계산 모델

알고리즘이란?

알고리즘은 컴퓨터 프로그램의 수학적 추상화이다. 어떤 문제를 해결하기 위한 계산 과정을 의미한다.

계산 모델(Model of Computation)

1. 임의 접근 머신(Random Access Machine; RAM)

RAM은 거대한 배열로 이루어진다. 각 배열의 요소 즉 레지스터는 하나의 워드(word)로 볼 수 있다.

상수 시간 O(1) 안에 할 수 있는 일들은 다음과 같다.

1. 레지스터 $r_{i}$에 존재하는 워드를 레지스터 $r_{j}$로 불러오기
2. 레지스터에서의 +,-,*,/,&,|,^ 연산
3. 레지스터 $r_{j}$를 $r_{i}$에 있는 메모리에 저장

이러한 RAM은 추상적 개념을 현실적으로 구현하는 모델이다.

2. 포인터 머신(Pointer Machine)

포인터 머신은 동적으로 할당된 객체로 이루어진다.

객체는 (대부분의 경우) 상수개인 O(1)개의 필드를 갖는다. 이 필드는 워드와 같다.

포인터 머신을 RAM으로 구현할 수 있다.

3. 파이썬 모델(Python Model)

1. List

   파이썬에서의 리스트는 연결 리스트(linked list)가 아니라 배열(array)이다. 즉 RAM 방식도 사용한다.

   따라서 리스트의 요소를 접근하는 $L[i]$연산은 상수 시간을 가진다.

   $x$ in $L$ → 최대 모든 원소를 순회하므로 O(n)

   $len(L)$ → 원소가 삽입될 때마다 내장된 길이 정보를 업데이트하므로 O(1)

   $L.sort()$ → 비교 정렬을 사용하여 O(nlogn)

2. 객체

   파이썬은 상수 개의 속성(필드)를 가진 객체를 가진다. 즉 포인터 머신 방식도 사용한다.

   따라서 $x$ 객체의 $next$ 속성을 접근하는 $x.next$ 연산도 상수 시간을 가진다.

3. Dictionary

   해시 테이블로 구현한다. 대부분의 연산이 높은 확률로(with high probability) 상수 시간을 가진다.