랜덤알고리즘 (2) 썸네일형 리스트형 LRU보다 좋은 페이지 교체 알고리즘 (Randomized Marking Algorithm) 캐시 메모리(cache memory)는 프로세서와 주 메모리 사이에 위치한 용량은 작지만 속도는 빠른 저장 장치를 의미합니다. 이 장치의 용도는 어떤 프로세스가 동작할 때 많이 접근하는 자료를 저장해 두는 것이죠. 프로세스가 특정한 자료를 필요로 할 때 해당 자료가 최신의 상태로 캐시 메모리에 존재한다면, 주 메모리에 직접 접근하지 않고 캐시 메모리에 접근하여 자료를 가져옴으로써 상당한 시간적 이득을 꾀할 수 있습니다. 프로세스가 호출하는 자료의 단위를 페이지(page)라고 부르겠습니다. 만약 프로세스가 어떤 페이지를 필요로 하는데, 최신의 해당 페이지가 캐시 메모리에 존재하는 때를 캐시 히트(cache hit), 그렇지 않을 때를 캐시 미스(cache miss)라고 부릅니다. 전자의 경우에는 캐시 메모.. 랜덤 알고리즘과 알고리즘의 확률적 분석 (Randomized Algorithms & Probabilistic Analysis of Algorithms) 요새 알고리즘에 어떻게 확률론이 사용되는지를 공부하고 있습니다. 그러면서 예전에는 잘 몰랐거나 어렴풋이만 알던 내용들을 정확히 바로 잡고 있는데요. 그중에서도 가장 기본적인 내용을 하나 가볍게 짚고 넘어 가고자 합니다. 바로 랜덤 알고리즘(randomized algorithm)과 알고리즘의 확률적 분석(probabilistic analysis of algorithm)인데요. 결론을 미리 말씀 드리자면 둘은 서로 다릅니다. 랜덤 알고리즘은 확률 시행이 알고리즘의 내부에서 이루어지는 것을 지칭합니다. 대신 주어지는 입력에 대해서는 어떠한 가정도 존재하지 않죠. 확률 시행이 알고리즘의 내부에서 진행되니, 알고리즘은 동일한 입력에 대해서도 다른 결과를 출력할 수 있습니다. 이러한 알고리즘의 성능을 분석할 때는 .. 이전 1 다음
