시간복잡도 분할 상환 분석(동적 배열의 추가 연산)

 

---

동적 배열의 추가(append) 연산

 

동적 배열의 추가 연산의 시간 복잡도를 계산해보자

 

다음과 같은 배열에 새로운 데이터를 추가한다고 하자

 

 

두 가지 경우에 대해서 생각해 볼 수 있다

 

---

 

1. 배열에 남는 공간이 있을 때

 

이 경우는 그냥 빈 공간에 데이터를 저장하면 되므로 시간 복잡도는 O(1)이다

 

 

---

 

2. 배열이 꽉 찼을 때

 

이 경우는 기존의 배열보다 큰 배열을 만들고 기존 배열에서 새로운 배열로 값을 다 복사해야 된다

 

 

기존 배열의 0번 인덱스에 접근해서 값을 복사하고

 

새 배열의 0번 인덱스에 접근해서 값을 붙여 넣고...

 

이미 있던 n개의 데이터를 복사해야 되므로 O(n)이 되고

 

새로운 데이터를 추가해야 되므로 O(1)이 되어

 

총 O(n+1) = O(n)이 된다

 

---

 

정리

 

배열에 남는 공간이 있을 때: O(1)

 

배열이 꽉 찼을 때: O(n)

 

최악의 경우는 O(n)이므로 동적 배열의 추가 연산 시간 복잡도는 O(n)이다

 

 

하지만 이대로 추가 연산 시간 복잡도를 O(n)이라고 하기에는  뭔가 비합리적이다

 

O(1)은 자주 발생하고 O(n)은 가끔 발생한다

 

이런 상환에 대해서 시간 복잡도를 다르게 분석하는 방법이 있다

 

---

 

분할 상환 분석

 

분할 상환 분석은 연산은 n번 했을 때의 총시간을 n으로 나눠주는 할부의 개념이다

 

동적 배열의 추가 연산에 분할 상환 분석을 적용해보자

 

우선 동적 배열의 추가 연산에 걸리는 시간을 두 가지로 나눌 수 있다

 

1. 빈 인덱스에 새로운 데이터를 저장하는 시간

 

2. 기존 배열보다 큰 새 배열을 만들고 기존 데이터를 새 배열로 옮기는 시간

 

---

 

1. 빈 인덱스에 새로운 데이터를 저장하는 시간

 

빈 인덱스에 데이터를 저장하는 데 걸리는 시간은 1이다

 

동적 배열에 새로운 데이터를 n개 저장한다면

 

총 n의 시간이 걸리게 된다

 

---

 

2. 기존 데이터를 새 배열로 옮기는 시간

 

배열이 꽉 차게 되면 기존 배열보다 2배 큰 새 배열을 만든다고 가정해 보겠다

 

배열의 크기가 1인 배열에 n개의 데이터를 추가 연산해보자

 

1번째 데이터를 배열에 추가하고 2번째 데이터를 배열에 추가할 때는

배열의 크기가 2인 새 배열을 만들고 기존의 1번째 데이터를 새 배열로 옮겨야 된다

이 과정에서 걸리는 시간은 1이다

 

3번째 데이터를 추가할 때는 배열의 크기가 4인 새 배열을 만들고 위의 과정을 반복해야 한다

이 과정에서 걸리는 시간은 2이고, 기존 데이터를 새 배열로 옮기는 총 걸리는 시간은 1+2이다

 

5번째 데이터를 추가할 때는 4의 시간이 걸리게 되고, 총 걸리는 시간은 1+2+4이다

 

9번째 데이터를 추가할 때는 8의 시간이 걸리게 되고, 총 걸리는 시간은 1+2+4+8이다...

 

새로 저장할 데이터가 n번째 데이터이고 이미 m개의 데이터가 저장되어 있다면

 

n번째 데이터를 추가할 때는 m의 시간이 걸리게 되고,

총 걸리는 시간은 m+m/2+m/4+...+1이 된다

이는 2m-1이 되며 항상 2n보다 항상 작다

 

이를 간단히 정리하면 n번째 데이터를 추가할 때

새 배열의 기존 데이터를 옮기는데 걸리는 총시간은 2n보다 적게 걸린다

 

---

 

최종 정리

 

n개의 데이터를 동적 배열에 추가 연산할 경우

 

1. 빈 인덱스에 새로운 데이터를 저장하는 시간 -> n

 

2. 기존 배열보다 큰 새 배열을 만들고 기존 데이터를 새 배열로 옮기는 시간 -> 2n보다 적은 시간

 

이 두 경우를 합치면 총 O(3n), 즉 O(n)이 된다

 

근데 이는 추가 연산을 연속으로 n번 할 경우에 걸리는 시간이다

 

추가 연산을 한번 하는데 걸리는 시간은 O(n)/n이 되어 결과적으로 O(1)이 된다

 

우리는 동적 배열의 추가 연산이 최악의 경우 O(n)이라는 것을 알고 있고

 

분할 상환 분석을 하면 O(1)이라는 것도 알고 있다

 

"동적 배열의 추가 연산이 최악의 경우에는 O(n)이 걸리지만 분할 상환 분석을 하면 O(1)이 걸린다"라고 표현할 수 있다

 

---