소오설 소오설

Growing and Shrinking Resize() method는 꽤 직관적이다. 크기가 기존 mSize의 두 배인 새로운 배열(resizedArray)을 만들고 mSize개의 원소를 새로운 배열에 복사한다. 그리고 Array Stack class의 mArr가 resizedArray를 가리키게 만든다. Resize() 시간을 계산하는 것은 어렵지 않다. 2*mSize의 새로운 배열 resizedArray를 만들고 mSize개의 원소를 복사한다. 따라서, O(mSize)의 time을 요구한다. 전의 Running time을 계산할 땐 이 Resize()를 무시했다. 여기서는 Amortised analysis기법을 사용하여 분석해보기로 한다. 이것을 통해서 Add/Remove가 각각 수행될 비용을 계산하..

Array Based List 이번 장에선 Array를 사용하여 정보를 저장하는 List와 Queue의 Interfece에 대해 공부할 것입니다. 후에 Interface의 공통된 Operation을 정리하는데 기본적으로 List interface는 다음과 같은 네 가지의 기능을 제공합니다. Get, Set, Add, Remove. 다음은 각각의 Data Structure의 각 Operation에 대한 Running time을 나타낸 표입니다. 단일 배열을 사용하여 정보를 저장하는 자료구조는 공통적인 장단점이 존재합니다. 1. 배열은 격납된 어떤 정보든 접근하는데에 상수시간만을 요구합니다. 덕분에 Get(i)와 Set(i, x)의 수행시간도 상수 시간 내에 해결을 할 수 있게 됩니다. 2. 배열은 Dyna..