시간복잡도 계산에서 기본적인 내용인 배열에 관련된 내용이다.
파이썬에서 [ ] 기호는 리스트의 literal이다.
listA = [1, 2, 3]그러나 파이썬의 엄마? 아빠? 언어인 C에서 [ ]는 리스트가 아닌 배열이라고 한다.
int staticArray[10];파이썬과 C에서 가장 큰 차이점은 바로 정적 배열이냐, 동적 배열이냐가 될 것이다.
정적 배열 (static array)
정적 배열은 그 크기가 정해져 있는 배열을 말한다. 즉, 위의 그림에서 배열을 정의할 때 4라고 정의했으면, 새로운 메모리 주소에 배열을 할당하지 않는 이상 그 크기를 바꿀 수 없다.
또한 요소가 메모리에 연속되어 저장되어 있어서 인덱스를 사용하여 데이터에 빠르게 접근할 수 있다. 인덱스를 통해 원하는 위치에 직접 액세스할 수 있기 때문에 데이터 검색 및 업데이트가 효율적.
(예: 정수의 크기는 4byte, 배열의 주소가 10000일 때 3번째 정수의 메모리 주소는 10000 + 3*4 = 10012이다)
반대로 파이썬에서는 여기저기 흩어져 있다.
데이터의 크기가 자주 변하지 않으면 정적 배열로 데이터를 저장하는 것이 적합하다.
동적 배열 (dynamic array)
동적 배열은 정적 배열과 반대로 개발자가 배열의 크기를 늘릴 수도 있고, 줄일 수도 있다. 파이썬에서 자주 사용되는 연산 append, pop을 쉽게 떠올릴 수 있을 것이다.
데이터의 크기가 자주 변하거나 업데이트될 때엔 동적 배열로 데이터를 저장하는 것이 적합하다.
정적 배열과 동적 배열의 시간복잡도
우리가 정적 배열과 동적 배열의 차이를 알고자 하는 것은, 바로 배열 연산에서의 시간복잡도를 비교하기 위한 것일거다.
접근 (access)과 탐색 (search)
먼저 접근과 탐색에 대한 개념을 알아야 한다. 접근은 주어진 인덱스에 접근하는 것이고 탐색은 주어진 요소가 어느 인덱스에 있는지 찾는 것이다. 따라서 접근은 O(1) 가 걸리지만, 탐색은 주어진 요소와 해당 요소가 일치하는지 일일이 확인해야 하기 때문에 최악의 경우 O(n) 이 소요된다.
정적 배열과 동적 배열 모두 접근과 탐색의 시간복잡도가 위와 같다.
삽입 (insert)과 삭제 (delete)
반면에 삽입과 삭제의 경우 배열을 수정하는 것이다.
만약 정적 배열에 할당된 메모리 중 남은 공간이 있다면 삽입할 수 있을테지만, 사실 그런 경우는 드물 것이다... 더욱이 C의 정적 배열은 다른 자료형은 저장할 수 없기 때문에, None이나 Null을 삭제한답시고 넣을 수도 없는 노릇이다.
따라서 정적 배열에서는 삽입과 삭제가 불가하다. 다른 메모리에 할당하여 새로운 배열을 만들어야 한다.
하지만 동적 배열은 다르다. 동적 배열은 저장하는 메모리의 크기를 키웠다 줄였다하는 것이 가능하다.
그러나 이것은 기존의 메모리 공간에서 한 칸 더 차지하고 덜 차지하고의 문제가 아니라, 아예 새로운 메모리 공간인데 기존 메모리 공간의 2배를 가지고 있는 공간을 예약하는 문제이다. 2배의 공간이 예약이 되면, 기존의 데이터를 복사한다. (이 역시 사실 n번 반복하기 때문에 O(n) 이 되지만, 분할 상환을 적용하면 O(1) 이 된다.)
다시 돌아와서... 삽입을 한다고 하면, 최악의 경우에는 O(n) (0번 인덱스에 새로운 요소를 삽입해서 나머지 요소들이 한 칸씩 뒤로 밀려야 함) 이 걸리고 최고의 경우에는 O(1) (분할 상환 분석 적용, 그냥 마지막에 추가하기)가 걸린다. 삭제의 경우에도 마찬가지다.
동적 배열에서는 삽입과 삭제가 가능하다.
