동적 배열 증분 계수(상환 분석) 계산기
초기 용량과 증분 계수(1.5배·2배 등)를 넣으면 목표 크기까지 재할당 횟수·총 복사 연산 수·평균(상환) 삽입 비용·낭비되는 메모리를 계산합니다. 배열이 커질 때 상환 분석이 어떻게 O(1) 삽입을 보장하는지 구체적인 숫자로 보여줍니다.
평균(상환) 삽입 비용
2.023회 연산/삽입
원소 1,000개를 넣는 데 총 쓰기 1,000회 + 복사 1,023회
재할당 기록 (앞 40건)
| # | 삽입 순번 | 용량 변화 | 복사 원소 수 |
|---|---|---|---|
| 1 | 2번째 | 1 → 2 | 1 |
| 2 | 3번째 | 2 → 4 | 2 |
| 3 | 5번째 | 4 → 8 | 4 |
| 4 | 9번째 | 8 → 16 | 8 |
| 5 | 17번째 | 16 → 32 | 16 |
| 6 | 33번째 | 32 → 64 | 32 |
| 7 | 65번째 | 64 → 128 | 64 |
| 8 | 129번째 | 128 → 256 | 128 |
| 9 | 257번째 | 256 → 512 | 256 |
| 10 | 513번째 | 512 → 1,024 | 512 |
사용 방법
- 1초기 용량과 증분 계수(예: 1.5, 2)를 정합니다.
- 2목표 크기(최종적으로 넣을 원소 개수)를 정합니다.
- 3재할당이 몇 번 일어나고, 그때마다 얼마나 복사되는지 표로 확인합니다.
- 4평균(상환) 삽입 비용과 낭비되는 메모리 칸 수를 봅니다.
자주 묻는 질문
배열이 꽉 찼을 때 새 용량을 현재 용량의 몇 배로 늘릴지 정하는 값입니다. 예를 들어 계수 2면 용량이 1→2→4→8처럼 두 배씩 늘어납니다. Java의 ArrayList는 1.5배, C++의 std::vector 구현체는 대개 2배를 씁니다.
한 칸씩 늘리면 삽입마다 매번 전체를 복사해야 해서 n번 삽입에 총 O(n²)이 듭니다. 배수로 늘리면 재할당이 갈수록 드물어져(용량이 지수적으로 커지므로) 총 복사량이 삽입 횟수에 비례하게 되고, 그 결과 삽입 한 번의 평균(상환) 비용이 O(1)이 됩니다.
개별 삽입 하나하나는 비용이 들쭉날쭉하지만(대부분 O(1), 가끔 재할당 때 O(n)), n번의 삽입 전체를 n으로 나눈 평균 비용은 일정하게 유지된다는 뜻입니다. 이 계산기의 "평균(상환) 삽입 비용"이 바로 그 값(총 쓰기+총 복사)/목표 크기입니다.
됩니다만 비효율적입니다. 계수가 1에 가까울수록 재할당이 훨씬 자주 일어나고, 재할당 횟수 자체가 늘어나면서 총 복사량이 원소 개수에 비례하지 않고 더 빠르게 커집니다. 그래서 실무 구현체는 대개 1.5~2 사이의 값을 씁니다.
용량은 항상 목표 크기 이상으로 «올림» 처리되기 때문에(예: 계수 2로 9개를 넣으면 용량은 16이 됩니다) 실제로 쓰지 않는 빈 칸이 남습니다. 계수가 클수록 재할당 후 남는 빈 칸(낭비되는 메모리)도 커지는 맞바꿈 관계입니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 재할당 시점만 건너뛰며 계산하는 빠른 경로를 씁니다 — 목표 크기가 10억이어도 재할당 횟수(대개 수십 회)만큼만 계산합니다.
- 새 용량은 현재 용량 × 증분 계수를 올림(⌈⌉)한 값입니다. 실제 언어·라이브러리 구현체는 세부 반올림 규칙이 조금씩 다를 수 있습니다.
- 증분 계수가 1 이하이면서 초기 용량만으로 목표 크기를 채울 수 없으면 재할당이 끝나지 않아 에러로 처리합니다.
- 이 계산기는 dev/big-o가 다루는 O(1) 상환 삽입이라는 점근 표기가 구체적으로 어떤 재할당 횟수·복사 횟수로 이어지는지 보여주는 응용 사례입니다.
- 입력한 값은 브라우저 안에서만 계산되며 서버로 전송되지 않습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 3일 · 결과는 참고용 추정치입니다.