[자료구조] 파이썬 리스트 (동적 배열) 정의 크기 시간복잡도 분할 상환 분석 비교, 삽입 연산

정적 배열 : 크기 고정(요소 수 제한, 보통 배열 지칭)

동적 배열 :  크기 변함(요소 계속 추가 가능) 

 

사실 이미 동적 배열을 사용하고 있는데, 파이썬의 리스트가 동적 배열이다. 

int_list = [2, 3, 5, 7, 11]

여기에 새로운 값을 추가할 수도 있다.

int_list.append(13)

 

우리 입장에서는 내부적으로 얼마나 큰 배열이 있는지 몰라도, 값을 마음대로 추가할 수 있다. 동적 배열이기 때문에 상황에 맞게 배열 크기가 조절되고 있는 것이다.

 

그럼 리스트를 사용할 때 현재 내부적으로 사용되고 있는 배열의 크기를 모른다. 아무리 저장한 데이터가 6개여도 내부적으로는 8개짜리 배열일 수도 있고, 12개짜리 배열일 수도 있고.. 알수가 없다.

 

그럼 만약 리스트의 길이를 출력하면 뭐가 나올까? len 함수를 쓰면 길이를 알수 있다.

print(len(int_list))

 

출력되는 결과는 

6

 

6이라고 나오는데, 실제 사용하고 있는 메모리 공간이 더 많을지라도, 파이썬은 개수를 셀 때 값을 저장해 놓은 공간에 대해서만 알려준다. 그래서 우리는 나머지 공간에 대해서 전혀 신경을 안써도 된다.

 

오히려 채워지지 않은 공간을 접근하려고 하면 오류가 난다.

 

 

동적배열의 추가 연산 시간복잡도

경우 1 : 정적 배열 남는 공간 있을때 -> 남는 공간에 그대로 추가 -> O(1)

경우 2 : 정적 배열이 꽉 찼을 때 -> n 개의 배열을 새 배열로 하나씩 복사 -> O(n)

 

 

분할 상환 분석 

① 같은 동작을 n번 했을 때 드는 시간이 X일 때, 동작을 한 번 하는 데 걸린 시간 : X/n

② 시간 복잡도를 평균으로 이야기 하는 것

 

동적 배열 동작

동적 배열에 추가를 할 때는

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

(2) 기존 배열의 크기가 부족해서 더 큰 배열을 만들고, 기존 배열의 데이터들을 옮기는 시간

 

이 두가지를 나눠서 생각하면 편하다. 우선 기억을 상기시키기 위해서 동적 배열에 데이터를 추가할 때 일어나는 일들을 쭉 나열해보면 비어 있는 동적 배열에 추가 연산을 9번 한다고 가정한다. 처음 시작할 때 동적 배열은 크기가 1인 배열이다.

 

1. 첫 번째 요소 추가 :

    1. 그냥 새로운 데이터를 저장한다.

2. 두 번째 요소 추가 :

    1. 배열이 꽉 찼습니다. 크기가 2인 배열을 새로 만들고 기존 데이터를 옮겨 저장합니다 (1 개 옮겨 저장)

    2. 맨 뒤 인덱스에 새로운 데이터를 저장한다.

3. 세 번째 요소 추가:

    1. 배열이 꽉찼다. 크기가 4인 배열을 새로 만들고 기존 데이터를 옮겨 저장합니다 (2 개 옮겨 저장)

    2. 맨 뒤 인덱스에 새로운 데이터를 저장한다.

4. 네 번째 요소 추가

    1 . 맨 뒤 인덱스에 새로운 데이터를 저장한다.

5. 다섯 번째 요소 추가

    1.  배열이 꽉 찼습니다. 크기가 8인 배열을 새로 만들고 기존 데이터를 옮겨 저장합니다 (4 개 옮겨 저장)

    2.  맨 뒤 인덱스에 새로운 데이터를 저장한다.

6. 여섯 번째 요소 추가

    1.  맨 뒤 인덱스에 새로운 데이터를 저장한다.

7. 일곱 번째 요소 추가

    1.  맨 뒤 인덱스에 새로운 데이터를 저장한다.

8. 여덟 번째 요소 추가

    1.  맨 뒤 인덱스에 새로운 데이터를 저장한다.

9. 아홉 번째 요소 추가

    1. 배열이 꽉 찼습니다. 크기가 16인 배열을 새로 만들고 기존 데이터를 옮겨 저장합니다 (8 개 옮겨 저장)

    2. 맨 뒤 인덱스에 새로운 데이터를 저장한다.

 

이런 식으로 내부 배열이 꽉 찼을 떄는 새로운 배열을 만들고 기존 요소들을 복사하고, 새로운 요소를 저장하면 된다. 그리고 배열에 여유가 있으면 그냥 새로운 요소만 저장하면 된다.

 

 

분할상환 분석을 하면 이 동장을 n번 반복한다고 가정한다. 총 걸리는 시간을 계산기에 쉽게 두 가지로 나눠서 생각해 볼거라고 했는데,

 

1. 새로운 데이터를 동적 배열 맨 끝에 단순히 저장하는데 걸리는 시간

2. 더 큰 배열을 만들고 그 배열에 기존의 데이터를 옮기는데 걸리는 시간

 

걸리는 두 시간을 각각 따로 계산해 본다.

 

배열 끝에 새로운 데이터 저장하는 데 걸리는 시간

x 번째 추가	배열 끝에 데이터 저장하는 데 걸리는 시간
1	1
2	1
3	1
4	1
5	1
6	1
7	1
...	1
n	1

 

인덱스에 데이터를 저장하는 데 걸리는 시간은 1이라고 했잖아요? 이걸 총 n 번 하는 거니까 O(n)이 걸릴 것이다.

 

새로운 배열에 데이터 옮기는 시간

이번에는 내부 배열이 꽉 차서 기존 데이터를 복사하는 데 걸리는 시간에 대해서 생각해 보겠다.

x번째 추가	배열 크기	새로운 배열에 요소 옮겨 저장하는 데 걸린 시간
1	1	0
2	2	1
3	4	2
4	4	0
5	8	4
6	8	0
7	8	0
...		0
n

 

새로운 배열에 기존 데이터를 옮겨 저장하는 시간은 위 표에 나와 있는대로 소요된다.

 

표를 살펴봅시다. 2 번째, 3 번째, 5 번째, 9 번째 추가 때 배열의 크기를 늘려야 합니다. 그럴 때 마다 데이터를 옮겨야 하는데요. 이때 데이터를 각각 1,2,4,8 개씩 복사하고 붙여 넣는다.

 

데이터를 복사해서 붙여 넣는 총 시간 비용은 이 시간들을 더한 8 +4 + 2 + 1인데요. 좀더 일반화해서 생각해보면

 

추가 연산을 n번 했을 때, 가장 마지막에 데이터를 m개 옮겨서 저장했다고 하자.

 

그럼 데이터를 복사해서 저장하는 데 걸린 총시간은 m + m/2 + m/4 + ... + 1 이렇게 표현 할 수 있다. 이걸 도형으로 나타내본다. 이런 식으로 처음에 m이있고 그다음에 계속 반으로 줄어든 값을 더해 주겠다.

 

 

 

처음에 이렇게 더해주다가, 결국에는 이렇게 될텐데

 

도형에서 볼 수 있듯이 이런 식으로 어느 자연수든 반씩 줄여서 1까지 계속 더해주면 그 결과는 절대 2m을 넘을 수 없다. 정확히 말하면 딱 2m-1이 된다.

 

근데 가장 최근에 데이터를 옮겨 저장할 때 8이 걸렸다는 건 무슨 의미일까? 원래 배열의 수용 가능 크기가 8이었지만 크기가 부족해서 16개의 데이터를 담을 수 있는 새로운 배열로 복사했다는 얘기인데. 그럼 결국에 현재 배열 안에 있는 데이터는 9개에서 16개 사이라는 말이다. 16개보다 더 많은 요소가 있으면 가장 최근에 옮겨 저장한 요소의 수가 8이 아니라 16이겠죠?

 

이 사실을 바탕으로 우리가 일반화할 때 사용했던 배열 안 요소 수 n과 가장 최근 옮겨 저장한 요소 수 m의 관계에 대해서 한 가지 사실을 알아낼 수 있는데

 

가장 최근에 복사하는 데 걸린 시간이 8일 때, 배열 안에 있는 데이터는 9개에서 16개 사이입니다. 즉, m은 무조건 n보다 작다고 할 수 있다.

 

추가 연산을 연속으로 n번 하고, 가장 마지막에 옮겨 저장한 데이터 요소 수를 m이라고 할 때:

(1) 복사해서 저장하는 데 걸리는 총 시간이 2m -1 이고

(2) m은 n보다 작다.

 

이걸 다시 정리해서 나타내면

연속으로 추가 연산을 n번을 하면 데이터를 옮겨서 저장하는 데 걸리는 총 시간은 2n 보다 작다!

 

 

두 경우 합치기

 

지금까지 나온 내용을 종합해 보면, 동적 배열에 n개의 데이터를 연속으로 추가하면:

 

1. 새로운 데이터를 저장하는 데에는 n의 시간이 들고

2. 데이터를 옮겨 저장하는 데에는 2n보다 적은 시간이 걸리는데요.

 

이 두 시간을 합치면 총 드는 시간은 3n보다 적은 시간이 걸릴 것이다. 이걸 시간 복잡도로 표현하면 O(3n), 그러니까 O(n)이라고 할 수 있다.

 

근데 이건 추가 연산을 한 번 하는 게 아니라 연속으로 n 번 하는 데 걸리는 시간 복잡도이다.

 

그러니까 총 n 번의 추가 연산을 하는 데 걸리는 시간이 O(n)인 건데, 추가 연산을 n 번 하는 데 O(n)의 시간이 걸리니까 1 번 하는 데는 O(n)/ n ​, 즉 O(1)이 걸리는 것이다.. 전에는 추가 연산이 최악의 경우 O(n)이 걸린다고 했었는데, 분할 상환 분석을 하면 O(1)이 걸린다고 보는 거죠.

 

 

최악의 경우 분석 vs. 분할 상환 분석 뭘 쓰면 되는 걸까

 

사실 분할 상환 분석을 한다고 꼭 시간 복잡도가 줄어드는 건 아니다. 보통은 할부 개념을 적용해도 시간 복잡도가 줄어들지 않는다. 하지만 만약 최악의 경우보다 분할 상환 분석을 한 시간 복잡도가 더 적다면, 분할 상환 분석을 한 시간 복잡도를 사용한다. 그러니까 “동적 배열의 끝에 데이터를 추가할 때는 O(1)이 걸린다.”라고 표현해도 된다는 것이다.

 

 

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

 

 

삽입 연산

- 경우 1 : 정적 배열 남는 공간 있을 때 (인덱스 지정에 따라 데이터가 뒤로 밀림) , 시간복잡도 : O(n)

- 경우 2 : 정적 배열 이 꽉 찼을 때 (새로운 배열을 만든 후, 복사 후 데이터를 뒤로 미룸), 시간복잡도 : O(n)