[C# 자료구조] 동적 배열 구현 방식과 시간 복잡도

일부 수행에서 일어나는 비싼 수행 비용을 분산시켜 여러 다른 일반 수행들로

분할 상환하여 비용을 계산하는 방식을 분할상환분석(Amortized Analysis)이라 부른다.

 

이러한 분석을 통해 배열을 하나씩 증가하는 동적 배열 방식 (수행시간이 O(n))보다

배열을 2배 혹은 1.5배로 증가하는 방식이 (수행시간이 O(1))이 훨씬 효율적임을 알 수 있다.