[Python Datastructure ] 배열 - appen operation 시간복잡도 with 분할상환분석

<appen operation 시간 복잡도 - 분할상환 분석>

• 정적 배열 : 배열의 길이가 정해져서 변하지 않는 배열
• 동적 배열 (dynamic array) : 배열의 길이가 동적으로 변하는 배열: 배열이 꽉 찼을 때 다른 메모리 공간에 기존 배열 크기의 두 배의 공간을 할당하고, 기존 배열을 복사하는 형식으로 내부적으로 공간을 늘린다
• 동적 배열은 내부적으로는 정적 배열을 기반으로 한 자료구조라고 한다.
  

  

그림출처

• 추가 연산 (append operation) 시간 복잡도
• append는 아래의 그림과 같이 배열의 끝에 요소를 추가해주는 연산이다.
  
  

그림출처

• 동적 배열에 값을 추가할 때 시간 복잡도를 알아보자

1. 경우 1 : 정적 배열 남는 공간 있을 때 단순히 index를 이용하여 접근하므로 O(1)이다.
2. 겨우 2: 정적 배열이 꽉 찼을 때 값을 추가하기 위해 현재 사용 중인 배열보다 더 큰 메모리를 할당하고 기존 값을 복사한 후 새로운 값을 추가하게 된다. n개의 데이터를 복사하고 새 배열에 붙여 넣는 과정을 n번을 진행하므로 O(n)이다.

따라서, 동적 배열에 값을 추가하는 연산은 최고의 경우 O(1), 최악의 경우 O(n)이 된다.

시간 복잡도를 표현할 때에는 보통 보수적으로 최악의경우를 따진다. 하지만, 동적 배열의 append 연산의 최악의 경우는 동적 배열의 메모리가 다 차있을 때이고 이런 경우는 자주 일어나지 않는다고는 한다.

이런 경우를 위해 시간복잡도를 계산하는 다른 방법이 존재한다.

분할 상환 분석 (Amortized Analysis)

참고사이트

분할상환 분석은 시간 복잡도를 최악의 경우가 아닌 평균을 내서 측정한다. 동적 배열과 같이 최악의 경우가 자주 이어나지 않는 경우에는 조금 더 합리적인 시간 복잡도를 구할 수 있다.

1. worst-case의 시간 복잡도 T(n)을 구한다.
2. 연산의 수로 나눈다
   • 위에서 예로 들었던 동적 배열의 append() 연산의 경우
   1. 새로운 데이터를 동적 배열 맨 끝에 저장하는데 걸리는 시간
      index에 데이터를 저장하는데 걸리는 시간 —> O(1)이고 n개의 데이터를 저장할 경우에는 O(n)이다.
      
      
   2. 더 큰 배열을 만들고 그 배열에 기존 데이터를 옮기는데 걸리는 시간
      추가 연산을 n번 했을 때 , 가장 마지막에 데이터를 m개 옮겨서 저장할 경우, 데이터를 복사해서 저장하는데 걸리는 시간은 m+1/2m + 1/4m + 1/8m +.... 이다. 이는, 배열의 메모리를 늘릴 때 기존 메모리의 2배씩 늘리기 때문이다. 등비수열의 합을 구하고 극한을 적용하면 계산이 된다.
      
      데이터 한 개를 옮겨서 저장하는 게 1이 걸린다고 가정해보자. 2개의 데이터를 옮기는 시간은 2, 4개의 데이터를 옮기는 시간은 4이다. 그리고 메모리가 다 차서 생성한 새로운 메모리의 크기는 기존 크기의 2배로 커진다.
   위의 식을 계산해보면 2m과는 가깝지만 2m보다 작은 값이 된다. 또한, 공간을 늘리는데 들인 시간이 8초가 걸렸을 경우는 이미 메모리가 8을 넘어 16개의 공간으로 늘렸다는 의미이다. 그러므로 배열 안의 요소 수 n과 최근에 옮겨 저장한 수 m의 관계는 m <n이라는 사실이다.

⇒ 결론적으로 추가 연산을 n번을 하면 데이터를 옮겨서 저장하는데 걸리는 총시간은 2n보다 작다고 할 수 있다.

두 경우를 합쳐보자

위의 내용을 종합하여 동적 배열에 n개의 데이터를 연속으로 추가한다면,

1. 새로운 데이터를 저장하는데 걸리는 시간 : n
2. 데이터를 옮겨 저장하는데 2n보다 적은 시간

1,2를 합치면 3n보다 적은 시간이 걸린다. —> O(3n) —> O(n)

위의 경우는 n번 하는데 걸리는 시간이므로 1번 하는데 걸리는 시간은 O(n)/n ⇒ O(1)이라고 할 수 있다.

보통 최악의 경우보다 분할 상환 분석을 했을 때 더 적다면 분할 상환 분석을 하 시간 복잡도를 사용한다고 한다.

결과 : 동정 배열의 추가연 산은 최악의 경우 O(n)이 걸리지만 분할 상환 분석을 하면 O(1)이 걸린다.