동적 배열(dynamic array)의 capacity 확장 전략에서, 일반적으로 1.5배 또는 2배로 증가시킵니다. 1.5배와 2배 성장 전략의 메모리 재사용 측면 트레이드오프를 설명하고, amortized O(1) append가 성립하는 이유를 분할 상환 분석 관점에서 설명해주세요.

동적 배열의 capacity 확장 전략에서 1.5배와 2배 증가는 메모리 재사용과 성능 간의 트레이드오프를 가집니다.

2배 증가는 더 자주 새로운 메모리 블록을 할당하게 되어 메모리 단편화를 유발할 수 있습니다. 반면, 1.5배 증가는 더 작은 단위로 확장하여 메모리 낭비를 줄일 수 있지만, 더 빈번한 재할당으로 인한 오버헤드가 발생합니다.

Amortized O(1) append는 분할 상환 분석으로 설명됩니다. append 연산 시 capacity가 부족하면 새로운 배열을 할당하고 기존 요소를 복사하는데, 이 비용은 O(n)입니다. 하지만 이 비용은 발생하지 않는 append 연산들로 분산됩니다. 예를 들어, 2배 성장 시, n개의 요소를 추가하는 데 총 비용은 대략 2n번의 복사로 amortized O(1)이 됩니다. 1.5배 성장도 유사하게 분석되며, 성장 인자가 클수록 재할당 빈도는 줄지만 개별 재할당 비용은 커집니다.