[ Open Data Structures ] - Array Stack - 2

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가 각각 수행될 비용을 계산하려는 것이 아니고, m번의 Add/Remove를 호출할 때 필요한 모든 Resize()의 비용을 계산하려는 것이다. 다음 Lemma를 증명할 것이다. 작성하다보니 mSize와 n이 혼용되어 사용되었다.

Summary

다음의 Theorem이 Array Stack의 Perfomance를 요약한다.

Theorem. Array Stack은 List interface를 Implement한다. Resize()의 호출을 무시한다면 Array Stack은 다음과 같은 Operation을 제공한다.

• Get(_i)와 Set(_i, _x)를 O(1)
• Add(_i, _x)와 Remove(_i)를 O( n - i + 1)

더 나아가서, 텅 빈 Array Stack에서 m번의 Add/Remove operation이 있었을 때, Resize()를 호출하며 발생하는 비용은 O(m)이다.

Array Stack은 Stack을 implement하기 적합하다. 특히, Push(_x)를 Add(_n, _x)로, Pop()을 Remove(_n - 1)로 구현할 수 있으며 이 과정들은 Amortised analysis로 O(1)에 수렴한다.

 

HiddenWriter/List at ArrayStack (github.com)