배열(array)

배열(array): 특정 크기만큼의 연속된 메모리 공간을 할당받는 자료형

 

배열의 특성

c언어 기준

• 자료형을 지정하고 선언
• 한 번 공간 크기가 정해지면 변경 불가
• 정수형 int로 배열을 선언할 때, 데이터의 사이즈는 컴파일러와 프로세서의 구조에 따라 다름
• int형은 과거에는 2바이트였다가 현재 32비트 이상의 시스템에서는 4바이트로 변경됨
• 배열의 각 엘리먼트의 주소는 사용된 자료형의 크기만큼 증가
• 배열은 특정 엘리먼트의 위치를 O(1)에 조회 가능
  배열의 크기가 얼마나 늘어나든 조회 속도에는 변함 X
  배열의 시작 주소에 (인덱스 x 자료형 크기)를 더해주면 해당하는 배열의 주소를 쉽게 계산할 수 있기 때문

 

현실적으로 데이터의 크기를 정확히 예상하기 어렵다. 미리 할당해놓은 공간이 너무 작거나 클 수 있다.
이 문제를 해결하기 위해 배열의 크기를 필요에 따라 변경하는 동적배열이 등장했다.
파이썬의 리스트가 이에 해당한다.

 

 

 

동적배열의 특성

• 작은 공간으로 시작해서 공간이 부족할 때마다 크기를 키워서 재할당하는 방식
• 재할당하는 비율: 그로스 팩터(Growth Factor, 성장인자) - 언어마다 상이
  더블링(Doubling): 성장인자 = 2
• 파이썬의 그로스 팩터: 초반에는 2에서, 점차 1.125로 수렴

 

단순히 기존의 공간을 늘리는 것이 아니다.

더 큰 크기의 새로운 공간을 할당하고, 기존의 데이터를 복사하는 것이다. 따라서 O(n)의 시간복잡도를 띈다.
그러나 "최악의 경우의 평균적인 성능"을 구하는 분할 상환 분석에 따르면 O(1)이다.

 

---

References

파이썬 알고리즘 인터뷰 - 박상길 저
TCP School - 1차원 배열