배열 자료구조 정리
Categories: datastructures
동적 배열
dynamic array 라고 하며, 원소를 추가하면서 자동으로 크기가 2배씩 늘어나는 형태의 배열
정적 배열
크기가 고정되어있는 배열
int arr[4];
성능
접근
정적 배열, 동적 배열 모두 인덱스를 이용한 접근은 O(1) 가 소요된다.
왜그럴까?
배열의 대표적인 특징인 순차적 저장 때문이라고 볼 수 있다.
같은 선형 자료구조인 연결리스트와 비교했을때 가장 큰 차이점이, 연결리스트는 메모리 곳곳에 저장되어있는 반면, 배열은 메모리 상으로 순차적으로 저장 되어있는 것이다.
바로 이 특징 때문에 우리가 arr[3] 을 하면 O(1) 로 원소에 접근 할 수 있는 것이다.
예를 들어 arr 이라는 배열에 원소가 4개 (1,2,3,4) 있다고 치자.
int 는 크기가 4 바이트 이기 때문에 다음과 같은 형태로 저장될것이다.
1000 = 1
1004 = 2
1008 = 3
1012 = 4
이때 a = arr[3] 를 하면 왜 선형 시간 으로 접근이 가능한걸까?
단순 수학이라고 생각해도 될것 같다.
C 언어에서는 배열 자체가 어디 저장 되어있는지 확인해보면 첫번째 원소의 주소가 나오는것을 확인할 수 있을것이다.
즉, arr 의 주소랑 arr[0] 주소가 같은 것이다.
이 특징을 이용하면 인덱스로 접근하는것도 쉽다.
arr의 주소 + sizeof(원소) x i(인덱스)
를 하면 우리가 찾고자 하는 인덱스가 바로 나오기 때문이다.
즉, 우리가 찾고있던 인덱스는 3이기 때문에
arr의 주소(1000) + sizeof(int) x i(3) 주소에 있는 원소를 꺼내올 수 있다.
삽입/삭제
배열은 기본적으로 삽입/삭제 모두 O(N) 이 소요된다고 볼 수 있다.
단, 동적 배열의 가장 끝에 원소를 추가할때는 평균적으로 O(1) 이 소요되고 최악의 경우에만 O(N) 이 소요된다.
O(1) 이 나올 수 있는 이유는 바로 분할상환분석(amortized analysis) 때문이다.
분할상환분석(amortized analysis)
N 크기의 배열이 있다고 해보자.
그러면 N 크기가 될때까지, 배열의 크기가 두배로 커지고, 그때 원소들을 전부 복사해야되는 시점이 언제인지 분석해보자.
마지막 시점부터 거꾸로 생각을해보면 편하다.
우선 직전에 두배로 커졌을때는 N/2 개의 원소를 복사했을것이고.
그 전에는 N/4 , 그전에는 N/8 ..1이 될때까지 계속 반으로 주는 것을 볼 수 있다.
그걸 나열해보면
N/2 + N/4 + N/8 + N/16 + ... + 2 + 1
이런식으로 될 것이다.
이걸 다 더해비면 N 이 조금 안되는 것을 알 수 있다.
결론적으로 말하면, N 개의 원소를 삽입할때 총 O(N) 정도가 소요되는데, 각각의 삽입 자체는 O(1) 이 소요된다.