Rootish Array Stack
-
[ Open Data Structures ] - Rootish Array Stack - 1DataStructure 2021. 3. 6. 16:04
Rootish Array Stack Get and Set 이러한 방법을 토대로 Get과 Set을 직관적으로 작성할 수 있다. 가장 먼저 적절한 block b를 찾아내고 해당 block 내의 index i가 위치할 index j를 계산하면 된다. 마지막으로 호출한 각 함수마다 적절한 조치를 취하면 끝이다. 일반적으로 이 작업들은 Constant time내에 완료된다. Add and Remove Grow()에서 소모하는 시간을 제외하면 Add의 Running time은 Array Stack처럼 원소들의 위치를 교환하는 작업에 압도적으로 의존하게 된다. 따라서 Array Stack과 같은 O(1 + n - i )의 Running time을 갖는다. Remove는 Add와 비슷하게 동작한다. i+1, i+2, ..