배열(Static Array)
배열은 자료구조에서 메모리공간 기반 연속 방식의 가장 기본이 되는 자료형이다.
포인터 기반 연결 방식의 기본 자료형은 연결리스트이다.
추상 자료형(Abstract Data Type, ADT)의 대부분은 배열 또는 연결리스트를 기반으로 구현한다.
(스택, 큐 등 <- 배열 or 연결리스트로 구현)
C언어를 기준으로 배열은 크기를 지정하고 해당 크기만큼 연속된 메모리 공간을 할당 받는 자료형이다. 크기가 고정되어 한번 생성한 배열의 크기는 변경 불가능하다.
배열은 어느 위치에나 O(1)에 조회가 가능하다.
동적 배열(Dynamic Array)
배열은 고정된 크기만큼의 연속된 메모리의 할당으로 구현한다. 그러나 실제 데이터에서 전체 크기를 가늠하기란 쉽지가 않다. 너무 작게나 할당하여 부족하거나 너무 크게 할당하여 낭비되는 경우가 많다. 이러한 문제를 해결하기 위해 자동으로 리사이징 하는 동적 배열이 등장하게 되었다.
대부분의 프로그래밍 언어에서 동적 배열을 지원하며 파이썬에서는 리스트가 동적 배열 자료형이다. (자바: ArrayList, C++: std::vector)
(대부분의 동적 프로그래밍 언어들은 정적 배열을 지원하지 않으며, 파이썬도 [동적 배열]만 제공한다.)
동적 배열의 원리는 생성한 크기에 데이터가 다 채워지면 늘려주고 복사하는 식이다.
대개는 더블링(doubling)이라 하여 2배씩 늘려주는데, 파이썬의 경우 초반에만 2배이고 전체적으로 약 1.125배로 다른 언어에 비해 조금만 늘려가능 형태로 구현되었다.
삽입 시 할당된 메모리가 부족하여 더블링이 일어나는 경우 새로운 메모리 공간에 더 큰 크기의 배열을 할당하고 기존의 데이터를 복사하는 작업이 발생하므로O(n)의 비용이 발생한다.
따라서 더블링이 일어나는 최악의 경우 O(n)이 되지만 자주 발생하는 경우가 아니므로 기존의 배열과 동일하게 분할 상환 분석에 따른 O(1)으로 삽입가 가능하다. (앞 쪽으로 삽입하는 경우 O(n)의 비용 발생)
조회: O(1)
삽입: O(1), 더블링:O(n)
삭제: O(1)앞부분 추가: O(n)
앞부분 삭제: O(n)
-> 앞 공간을 비우거나 채우기 위해 요소들을 한번 씩 다 옮김
Reference)
파이썬 알고리즘 인터뷰
https://medium.com/@satorusasozaki/amortized-time-in-the-time-complexity-of-an-algorithm-6dd9a5d38045
