[자료구조] 동적, 정적 배열과 시간 복잡도 & 분할 상환 분석

배열 접근

파이썬의 list는 C언어의 배열을 따서 만들었다

차이점이 있다면 C배열은 1. 크기가 고정 2. 같은 타입의 데이터만 담을 수 있다.

 

C언어의 배열은 미리 순서적이고 연속적인 메모리 칸을 쓴다고 예약하고 값을 넣는다

Python의 list는 레퍼런스가 저장되어있고 값을 저장한다기보다는 가리킨다는 의미라서 값이 연속적일 수도 있고

연속적이지 않을 수 도 있다.

 

배열 탐색

 

배열 접근 연산 : O(1)

배열 탐색 연산 : O(n)

 

정적, 동적 배열

정적 배열 : 크기 고정 (요소 수 제한)

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

일반적으로 배열은 정적 배열이다.

 

동적배열은 정적 배열처럼 일정한 메모리를 확보한 후 값을 집어넣는 건데

메모리가 꽉 차면 늘리는 식으로 정적 배열의 크기를 상황에 맞게 조절하는 것이다.

 

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

경우 1 : 정적 배열 남는 공간이 있을 때 : O(1) <-- 최고의 경우, 자주 일어남

경우 2 : 정적 배열이 꽉 찼을 때 : O(n) <-- 최악의 경우, 가끔 일어남

---

분할 상환 분석(Amortized Analysis)

분할 상환 분석을 시간 복잡도를 평균 내서 구한다

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

 

동적 배열의 추가(append) 연산에 직접 분할 상환 분석을 해보자.

 

동적 배열에 추가를 할 때는 다음이 있다.

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. 기존 배열의 크기가 부족해서 더 큰 배열을 만들고, 기존 배열의 데이터들을 옮기는 시간

먼저 1번 배열 맨 끝에 새로운 데이터를 저장하는 시간을 보면

인덱스에 데이터를 저장하는데 걸리는 시간은 1이고 이것을 n번 반복하므로 O(n)이 걸린다.

이제 2번 기존 배열의 크기가 부족해서 더 큰 배열을 만들고, 기존 배열의 데이터들을 옮기는 시간을 계산해보자.

시간은 아래의 표만큼 소요된다.

그러면 데이터를 복사해서 붙여 넣는 총시간은 8 + 4 + 2 + 1 이 소요됐다.

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

---

위의 과정을 일반화 해서 생각해보자.

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

데이터를 복사해서 저장하는데 걸린 총 시간 = m + m/2 + m/4 + ... + 1이다. 이때 값은 2m을 넘을 수 없고 최대 2m-1까지만 된다. 그리고 배열안의 요소 수 n과 가장 최근 옮겨 저장한 요소 수 m의 관계에서 항상 m<n이다.

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

 

즉 1번 새로운 데이터를 저장하는 시간 = n, 2번 데이터를 옮겨 저장하는 시간 < 2n 이므로

두 시간을 합치면 3n보다 적은 시간이 걸린다. 이것을 시간 복잡도로 표현하면 O(3n) 즉 O(n)이라고 할 수 있다.

이것은 추가연산을 연속으로 n번 하는데 걸리는 시간이므로 추가연산을 1번 하는데는 O(1)이 걸린다.

 

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

 

---

동적 배열 삽입 연산(insert operation) 

추가 = append

삽입 = insertion

 

삽입 연산(insert operation) :

경우 1 : 정적 배열에 남는 공간이 있을 때 --> O(n)

- 삽입하고 싶은 인덱스 뒤의 요소를 한칸 씩 뒤로 미룬후 삽입한다.

- 이때 시간 복잡도는 O(n)+O(1) = O(n)이 걸린다.

경우 2 : 정적 배열이 꽉 찼을 때 --> O(n)

-  배열의 크기를 2배로 늘린 후 인덱스를 한칸 씩 뒤로 미룬후 삽입

-  이때 시간 복잡도는 O(n) + O(n) + O(1) = O(n)이 걸린다.

 

결과적으로 삽입 연산 시간 복잡도는 어떤 경우든 O(n)이 걸린다.

---

동적 배열 삭제 연산

삭제 연산 동작

2, 3, 5, 7, 11이 있는 동적 배열에서 인덱스 1에 있는 3을 지우고 싶다면 인덱스 뒤에 있는 데이터를 모두 한 칸씩 앞으로 밀어서 저장하면 된다.

2

3

5

7

11

2

5

7

11

동적 배열은 배열의 크기와 개발자가 사용하는 인덱스들의 범위를 따로 관리한다.

 

삭제 연산 시간 복잡도

삭 제연산의 시간 복잡도는 다음과 같이 2가지로 나눌 수 있다.

1. 맨앞의 데이터를 지울 때(최악의 경우) --> O(n)
2. 맨뒤의 데이터를 지울 때 -->O(1)

1. 맨앞의 데이터를 지울 때(최악의 경우) : 삭제 연산이 가장 오래 걸리는 경우이다.

가장 앞 데이터를 삭제할 때는 인덱스 1부터 끝까지 모든 요소들을 한 칸씩 앞으로 밀어서 저장해야 된다. 그러니까 삭제하기 전 배열 안에 총 n개의 데이터가 남아 있으면, 총 n-1개의 요소들을 하나씩 앞 칸으로 밀어서 저장해야 된다. 이 횟수가 n에 비례하므로 O(n)이 걸린다. 즉, 삭제 연산은 총 O(n)이 걸린다.

 

2. 맨뒤의 데이터를 지울 때

위에서는 일단 아무 위치에 있는 데이터를 삭제할 때는 최악의 경우 O(n)이 걸린다는것을 알아보았다.

맨 뒤 데이터를 삭제할 때는 아무 요소도 안 밀고 저장해도 되고, 그냥 동적 배열의 사용 공간을 한 인덱스 줄이면 된다..배열에 데이터 요소가 몇 개가 있는지에 상관이 없이 일정한 시간이므로 O(1)이다.

---

동적 배열 크기 줄이기

• 동적 배열의 크기를 줄이는 이유 : 낭비되는 메모리를 아끼기 위함
• 동적 배열의 크기를 줄이는 시점 : 내부 배열의 사용 비율이 특정 값 이하로 떨어질 때이다. 이 비율은 개발자나 프로그래밍 언어에 따라 다르다.

동적 배열 크기 줄이기 시간 복잡도 :

• 최악의 경우 : 더 작은 배열로 모든 요소들을 옮겨 저장해야 될 때이다. 배열 안에 있는 요소 수가 n개라고 가정하면, 총n개의 데이터를 모두 새 배열에 복사해서 넣어야한다. 맨 뒤 데이터를 삭제하는 건 O(1)이 걸린다. 하지만 n개의 데이터를 모두 새 배열에 복사해서 넣어야 되기 때문에 n에 비례하는 시간, O(n)이 걸린다.
• 맨 끝 데이터 삭제 분할 상환 : 하지만 내부 배열의 크기가 줄어드는 건( O(n) ) 드문 경우다. 대부분의 경우 그냥 마지막 인덱스에 있는 데이터를 지워 주기만( O(1) )  하면 된다. 분할 상환 분석을 하면 맨 끝 데이터를 삭제하는 연산은 O(1)이다. 

---

배열과 동적 배열 정리/ 비교

연산 & 시간 복잡도

	배열 시간복잡도	동적 배열 시간복잡도
접근(access)	O(1)	O(1)
탐색(search)	O(n)	O(n)
삽입(insert)	N/A	O(n), 맨뒤 O(1)
삭제(delete)	N/A	O(n), 맨뒤 O(1)

n = 배열 요소 수

 

낭비하는 공간

• 배열 : 크기가 고정되어 있기 때문에 낭비하는 공간이 없다.
• 동적 배열 : 공간을 낭비할 수도 있고 안 할 수도 있다. --> 최악의 경우 : O(n)

---

배열의 인덱스 주소 계산

배열은 데이터를 연속적이고 순차적으로 저장해 놓기 때문에

1. 배열의 시작 주소
2. 저장하는 자료형의 크기
3. 인덱스

이 세 가지만 알면 원하는 인덱스의 주소를 계산할 수 있다.

배열 시작의 주소 + (인덱스 * 저장하는 데이터 자료형 크기)

이렇게 원하는 인덱스의 주소를 O(1)으로 계산하면 되고, 이 주소로 해당 메모리에 접근할 수 있다.

 

예시) 배열 int_array의 주소가 10000이고, 정수 자료형의 크기가 4 바이트이면, int_array[300]의 주소를 계산해보자.

  답) 배열 시작의 주소 + (인덱스 * 저장하는 데이터 자료형 크기) = 10000 + (300 * 4) = 11200이다.