이진 카운터 편집하기 (부분)

==분할 상환 분석==
이진 카운터는 분할 상환 분석의 대표적인 예로 자주 인용된다. 하나의 증가 연산에서 여러 비트가 반전되기 때문에, 최악의 경우 O(log n)의 시간이 걸릴 수 있다. 그러나 일련의 연산 전체를 분석하면 평균적인 비용은 훨씬 낮다.

예를 들어 n번의 증가 연산이 있다고 가정하자. i번째 비트는 2ⁱ번마다 한 번씩 반전된다. 따라서 n번의 증가 동안 i번째 비트가 반전되는 횟수는 ⌊n / 2ⁱ⌋이다. 이를 모든 비트에 대해 합산하면 총 반전 횟수는 다음과 같다:
*총 반전 수 ≤ n(1/2 + 1/4 + 1/8 + …) < 2n
따라서 평균적으로 각 증가 연산당 비트 반전 횟수는 O(1)에 해당한다. 이는 분할 상환 분석의 aggregate method 또는 accounting method로 설명된다.

이러한 분석은 이진 카운터를 기반으로 한 자료구조(예: 동적 배열의 크기 조절, 최소 힙 삽입 등)의 평균 성능을 이해하는 데 중요한 도구가 된다.