Algorithm/자료구조
[배열] 분할 상환 분석 적용
분할 상환 분석은 연산을 n 번 했을 때 총 드는 시간 X를 n으로 나눠주는 “할부” 개념이라고 배웠는데요. 최악의 경우로 시간 복잡도를 얘기하는 것이 비합리적인 경우에 사용하죠. 이번 레슨에서는 동적 배열의 추가(append) 연산에 직접 분할 상환 분석을 해 봅시다. 동적 배열 동작 동적 배열에 추가를 할 때는: 새로운 인덱스에 데이터를 저장하는 시간 기존 배열의 크기가 부족해서 더 큰 배열을 만들고, 기존 배열의 데이터들을 옮기는 시간 이 두 가지를 나눠서 생각하면 편합니다. 우선 기억을 상기시키기 위해서 동적 배열에 데이터를 추가할 때 일어나는 일들을 쭉 나열해 볼게요. 비어 있는 동적 배열에 추가 연산을 9번 한다고 가정합시다. 처음 시작할 때 동적 배열은 크기가 1인 배열입니다. 첫 번째 요소..
