Randomisation and Probability
-
[ Open Data Structures ] - Randomisation and ProbabilityDataStructure 2021. 5. 6. 00:13
Randomisation and Probability 어떤 자료구조를 구현함에 있어서 앞으로 혹은 이전에 랜덤화를 채택하는 일이 있을 것(혹은 있었다)이다. 이 자료구조는 저장되는 자료나 수행되는 작업(Operation)에 대해 독립적인 무작위 선택을 차용한다. 이러한 연유로 같은 작업을 한 번 이상 수행하게 되면 각각 다른 결과를 얻게 된다. 이런 형태의 자료구조를 분석함에 있어서 우리는 이들의 Expected Running Time에 중점을 두게 될 것이다. 딱딱한 표현을 쓰자면 랜덤화 된 자료구조의 Running time은 Random Variable(랜덤 변수)이며 여기서는 그 랜덤 변수의 Expected value에 대한 공부를 하기로 한다. 셀 수 있는 집합 U 안에 있는 이산 랜덤 변수(Di..