아래의 n비트 정수 증가연산 슈도 코드를 보자

inc (x : Bool[n]) -> Bool[n] {
  c = 1
  i = 0
  while (i < n && c == 1) {
    c' = x[i] & c
    x[i] = x[i] ^ c
    c = c'
    i++
  }
  return x
}

만약 캐리 c = 0이 되면 이어지는 비트열에 대해서는 더이상 연산하지 않고 루프를 탈출함.

이 procedure의 시간 복잡도는 어떻게 될까?
비트가 역전되는 횟수를 세서 판단해보자.
x = 0000 일 때에는 첫번째 비트를 증가시키는 시점에서 c=0이 되기 때문에 비트는 1번 역전됨
하지만 x = 1111 이라면 4개의 비트를 모두 역전시켜야 함
그러니까 모든 비트가 1일때가 worst case고, 시간복잡도는 O(n) 이 됨을 알 수 있음

이번에는 이 증가연산을 어떤 x에 반복해서 2^n번 적용하는걸 생각해보자

앞에서 구한 개별 연산의 시간복잡도를 사용해서 총 시간복잡도를 구해보면, 총 증가연산을 2^n번 수행하고 각각의 시간복잡도가 O(n) 이므로 전체 시간복잡도는 O(n*2^n)이 됨.

하지만 잘 생각해보면, 모든 케이스가 worst-case 인 일은 발생할 수 없음. 1111에서 inc를 하면 0000이 되니 그 다음 연산은 1번의 비트 역전밖에 일어나지 않음!

그래서 이번에는 아래처럼 계산할꺼임
첫번째 비트는 1만큼 증가할때마다 바뀌니 총 2^n번
두번째 비트는 2만큼 증가할때마다 바뀌니 2^(n-1) 번
...
마지막 비트는 2^1번만 바뀐다.
모두 더하면
2 + 4 + ... + 2^n = 2^(n+1)-2
시간복잡도로 따지면 O(2^n)

그렇다면 이걸 2^n개의 각각의 증가연산에 분배해서 생각하면 실질적으로 각각의 연산에 소요되는 시간은 O(1)임을 알 수 있음

이게 amortized time complexity(분할상환시간) 임. 개별 연산의 worst case만을 따지는게 아니라 모든 연산을 수행했을때의 시간복잡도를 구하는거

그럼 평균 시간복잡도와는 뭐가 다른지 궁금할 수 있는데, 각각의 연산을 모두 종합했을 때 차이가 있음.
해쉬 테이블의 시간복잡도는 average는 O(1) 이지만 worst case는 O(n)이고, 해쉬테이블에 원소를 n개 삽입했을 때 실제로 O(n^2)의 시간이 걸릴 가능성이 있음.
하지만 분할상환 시간은 확률적 분석이 아니기 때문에 연산을 여러번 했을 때 worst case만 일어나는 일이 없음을 확신할 수 있음

반면 worst-case비교하면, average case와 마찬가지로 각각의 단일 연산에서의 수행시간은 보장해주지 못함.

그래서 함슬람들이 persistent data structure로 amortized O(1) queue 구현해놓고 자기합리화 할 때 많이 쓰임


깃붕이들 다 아는 이야기라 노잼일지도

- dc official App