Array 배열, List 리스트- Data Structure 1

Array 배열, List 리스트

시간 절감을 위해 작은 array 자료 구조(작은 메모리)를 설계 한경우!

=> 메모리를 낭비하지는 않으나, array 스케일을 자주 재설정해야하는 만큼 O(N) 의 시간 복잡도를 갖게 된다

 

처음부터 큰 메모리를 할당한 경우!

=> 처음에는 낭비하는 메모리가 많다. 그러나 메모리 사이즈를 재할당해야하는 경우가 적을 것이다.

 

공간(메모리) 복잡도와 시간 복잡도는 반비례 혹은 trade-off 의 관계이기에 최적화에 대해 고민할 일이 많다!

 

Data Structure, 자료구조 데이터 구조는 왜 필요할까?

 

item 추가하기

Array 메모리가 다 차지 않은 이상 array 의 끝에 연속적으로 item 을 추가할 수 있다.

시간 복잡도: O(1) 이라고 볼 수 있다. 바로 array 의 끝에 item 을 채우면 되기에 시간이 상수값으로 보면 된다

5

3

-9

7

array 가 꽉 차있다면?

그러면 당연히 item 을 추가할 수 없다. 현실에서는 이런 경우, RAM 용량을 늘리거나(보통 array 사이즈의 2배를 할당한다) 기존 array 의 item 을 하나하나 복사하여 새로운 array 에 복붙해야한다. 기존 array 의 길이(크기) 만큼의 시간에 비례하기에 시간 복잡도: O(n)에 해당한다. 

 

array 중간에 item 을 추가해야한다면?

위 array 의 3 이 있는 자리에 11을 추가하고 싶다면, 3 부터 그 뒤의 모든 숫자를 한칸씩 오른쪽으로 보내고 11을 기존 3의 자리에 채우는 개념이다. 시간 복잡도: O(n)

 

 

item 제거하기

array 끝자리의 item 을 제거하는 것은, 애초에 제일 끝이기 때문에 제거가 쉽다. 시간 복잡도 O(1)

 

array 중간에 item 을 제거해야한다면?

array 중간에 item 을 추가 할 때와 마찬가지로 item 제거로 인한 비는 자리를 채워야하기 때문에 한칸 씩 왼쪽으로 앞당기는 일이 발생하여 시간 복잡도 O(n)

 

index 로 item 의 위치를 찾는 것 또한 주어진 index 가 있기 때문에 array 를 훑을 필요가 없으므로 시간 복잡도 O(1)

 

 

List 리스트

 

Pyhton 에서는 통상적으로 array 를 list 로 칭하지만 list 는  array ds 가 아니다. (실제 array 는 Numpy 라는 python library 를 통하여 사용할 수 있다)

Python 의 빌트인 list ds 는 array 처럼 연속적인 메모리공간을 활용하지 않고 item 별로 메모리 내의 다른 공간들을 reference 하여 저장한다. 

 

List 시간 복잡도 정리표 참고하세요

TimeComplexity - Python Wiki