[배열] 배열의 자료구조

배열은 1차원도, 2차원도, 3차원도 메모리에 할당될 때는 메모리가 1차원이므로 메모리에 연속 할당된다.

 

1차원 배열은 낮은 주소에서 높은 주소로 연이어서 할당된다.

2차원 배열은 1행이 낮은 주소에서 높은 주소로 연이어서 할당된 후, 2행이 낮은 주소에서 높은 주소로 할당된다.

 

배열의 효율성

배열은 메모리에 임의 접근할 수 있으므로(메모리 특성상 주소를 특정해서 접근할 수 있으므로) 접근에는 시간 복잡도가 O(1)이다.

 

데이터의 추가, 삭제에는 어디에 있느냐에 따라 다르다.

맨 뒤에 추가할 때는 빈 자리에 그냥 넣으면 되므로 O(1).

그러나 맨 앞에 삽입하려면, 다른 녀석들을 한칸씩 뒤로 옮겨야 하므로 O(n)이 된다.

 

따라서 append(),pop() 연산은 O(1), pop(0) 연산은 O(n)이다.

하지만 insert(), remove() 또한 값을 찾아야 하므로 O(n)이다.

 

코딩테스트에서 메모리 크기를 잡는다면

정수형 1차원 배열은 1000만개

2차원 배열은 3000*3000개의 크기가 최대이다.

 

 

파이썬의 자료구조별 시간복잡도를 보고싶다면 여기

https://wayhome25.github.io/python/2017/06/14/time-complexity/