워드 램

이론 컴퓨터 과학에서, 단어 RAM(word random-access machine) 모델은 w비트의 단일 단어에서 비트 연산을 할 수 있는 랜덤 액세스 기계인 연산 모델이다.이 모델은 1990년 마이클 프레드먼과 댄 윌러드가 C와 같은 프로그래밍 언어를 시뮬레이션하기 위해 만들었다.^[1]

모델

RAM 모델이라는 단어는 랜덤 액세스 기계와 유사하지만 추가적인 기능을 가진 추상적인 기계다.w비트까지 크기의 단어와 함께 작동하는데, ${\displaystyle {이}^{}}$는 2 w ${\$까지 정수를 저장할 수 있다는 것을 의미한다$.$ 모델에서는 단어 크기가 문제 크기와 일치한다고 가정하기 때문에, 즉, 크기 n의 문제에 대해서는 $w{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle \mathrm{로그}}$ ${\displaystyle n}$ ${\displaystyle w\geq\log n$ 단어 RAM 모델은 transdichotomous 모델이다.이 모델은 산술적, 논리적인 이동과 같은 비트 연산들을 일정한 시간에 수행하도록 허용한다.^[2]가능한 값의 개수는 U이며, $여기$서 U ${\displaystyle \le }$ ${\displaystyle 2^{}}$ w ${\$U\$leq$ 2$^{w$

알고리즘 및 데이터 구조

RAM 모델이라는 단어에서 정수 정렬은 상당히 효율적으로 이루어질 수 있다.Yijie Han and Mikkel Thorup created a randomized algorithm to sort integers in expected time of (in Big O notation) ${\displaystyle O(n{\sqrt {\log \log n}})}$,^[3] while Han also created a deterministic variant with running time ${\displaystyle O(n\log \log n)}$.^[4]

동적 전임자 문제는 RAM 모델이라는 단어에서도 공통적으로 분석되며, 모델의 원래 동기가 되었다.Dan Willard는 O${\displaystyle (}$로그${\displaystyle }y{\displaystyle }$ ${\displaystyle \log }$ ${\displaystyle }$ ${\displaystyle U}$){\$displaystyle O(\log \log$ U$)}시간$ 내에 이 문제를$$ 해결하기 위해 y-fast trys를 사용했다$.$^[2]마이클 프레드먼과 윌러드도 $O{\displaystyle ({\mathrm{로그}}_{}}$ ${\displaystyle w_{}\mathrm{wn}}$ $){\displaystyle O(\log _{w}n)}$시간에$$ 퓨전 트리를 이용해 문제를 해결했다.^[1]

참고 항목

• 트랜스디코토머스 모형

참조