<삭제 연산 - 시간 복잡도 분석>
삭제 연산 동작
- 길이가 5인 리스트에서 index 1에 있는 요소를 지우고 싶은 경우
- 인덱스 1 뒤에 있는 데이터를 모두 한 칸씩 앞으로 밀어서 저장한다.
- 인덱스 1에 인덱스 2에 있는 요소를 저장한다
- 인덱스 2에 인덱스 3에 있는 요소를 저장한다
- 인덱스 3에 인덱스 4에 있는 요소를 저장한다
- 동적 배열에서 접근할 수 있는 인덱스 범위도 1을 줄여준다동적 배열은 배열의 크기와 개발자가 사용하는 인덱스들의 범위를 따로 관리한다.
삭제 연산 시간 복잡도
삭제 연산도 아무 위치에 있는 데이터를 삭제할 때와 맨 뒤 데이터를 삭제할 때, 두 경우도 나눠서 생각할 수 있다.
- 최악의 경우 : 맨 앞의 데이터를 지울 때
삭제 연산은 최악의 경우 삭제할 데이터가 맨 앞에 있는 경우이다. 인덱스 1부터 끝까지 모든 요소들을 한 칸씩 앞으로 밀어서 저장해야하기 때문이다.
배열안에 n개의 데이터가 있다면 총 n-1개의 요소들을 한 칸씩 앞으로 밀어서 저장해야하므로 O(n) 이 걸린다.
- 맨 뒤의 데이터를 지울 때
단순히 동적 배열의 사용 공간을 한 인덱스 줄이면 된다. 배열에 데이터가 몇 개가 있든 상관 없는 연산이므로 O(1)이라고 할 수 있다.
결론 : 아무 위치에 데이터를 삭제할 때: O(n) , 가장 뒤에 있는 데이터를 삭제할 때 : O(1)
<동적 배열의 크기>
동적 배열은 내부적으로 정해진 크기의 정적 배열을 사용한다. 값을 추가하다 내부 배열이 꽉 차면 더 큰 내부 배열을 사용하도록 자동으로 늘려준다. 반대로 값을 삭제할 때에도 배열의 크기를 줄이기도 한다. (내부 배열의 크기도 줄여서 공간을 효율적으로 사용하기 위함)
- 동적 배열은 요소의 개수가 어느정도 줄어들면 내부 배열의 크기를 조절한다.
- 크기를 줄이는 시점은 개발자나 프로그래밍 언어에 따라 비율이 다르다.
시간 복잡도
- 맨 끝 데이터 삭제 시간 복잡도
최악의 경우 : 작은 배열로 모든 요소들을 옮겨 저장할 때.
맨 뒤의 데이터를 삭제하는 것은 O(1)이지만 n개의 데이터를 모두 새 배열에 복사해서 넣기 때문애에 n에 비례하는 O(n)이 된다.
- 맨 끝 데이터 삭제 상환 분석
하지만, 대부분 마지막 인덱스만 지워주기만 하면 되므로 내부 배열의 크기가 줄어드는 경우는 거의 없다고한다.
따라서, 분할 상환 분석을 적용하면 맨 끝의 데이터 삭제 또한 O(1)이라고 할 수 있다.
결론 : 동적 배열에서 맨 끝 데이터를 삭제하는 연산은 최악의 경우 O(n)이 걸리지만, 분할 상환 분석을 적용하면 O(1)이라고 할 수 있다.
낭비되는 공간
- 배열은 낭비되는 공간이 없다.
- 반면 동적 배열은 정적 배열의 크기가 늘어날 떄
만약 수용 공간이 8개이고 8개의 요소가 들어가있을 때애는 낭비하는 공간이 없지만,
추가 삽입을 하려고 하면 정적 배열의 크기가 2배인 16개의 공간을 새로 추가하고 새로 추가된 데이터까지 총 9개의 요소가 들어가게 된다. 이떄 7개의 공간이 낭비되는 공간이다.
이 경우와 같은 최악의 경우 새로운 배열을 만들 때이며, 이 때 n개의 데이터가 배열에 있다면 n-2개의 공간이 낭비된다.
따라서, 낭비되는 공간은 최소 0~ n-2 까지이다.
