배열

C 의 배열에서는 실제 값들이 메모리에 들어오지만, 파이썬의 배열(리스트)에서는 실제 값이 들어오는 게 아니라 실제 값의 레퍼런스(주소) 값이 들어온다. 따라서 한 배열에 여러 가지 타입을 넣을 수도 있고, 실제 값의 크기도 중요하지 않다. 또한 메모리에 연속적으로 존재하지 않을 수도 있다.

C 배열

파이썬 배열

C배열과 파이썬배열의 자세히 알아보기 : http://www.laurentluce.com/posts/python-list-implementation/

배열 접근 vs. 탐색

배열의 접근

인덱스를 직접 지정해서 접근 (O(1))

배열의 탐색

찾고자하는 값의 인덱스를 모르는 상태에서 배열에서 원하는 값 탐색 (O(n))

배열 연산 시간 복잡도

추가 연산(append operation)

파이썬의 배열은 내부적으로 C언어의 정적배열을 사용한다.

그러다가 배열의 사이즈가 더 커져야한다면, 두 배로 큰 메모리 공간을 예약해서 사용한다.

배열의 추가연산은 두 가지 케이스가 있다.

case1. 배열에 공간이 남아있을 때

그냥 비어있는 배열 공간에 인덱스를 이용해 접근하면 되는 것이므로 O(1) 이다.

case2. 배열에 공간이 없을 때(=꽉 찼을 때)

데이터를 추가하기 위해서 현재 사용 중인 배열보다 두 배 큰 메모리의 배열로 옮겨야 한다.

기존 배열에서 새로운 배열(메모리 2배)로 값을 싹 다 복사하는 작업이 필요하다.

따라서 n개의 데이터를 새 배열에 복사하는 작업 O(n) + 새로운 데이터 하나 추가 O(1)

결과적으로 O(n) 이다.

분할 상환 분석

시간복잡도 계산 시, 최악의 경우를 가정하긴 하지만 최악의 경우가 나올 확률이 매우 적을 시에는 이는 불합리할 수도 있다. 이를 해결하기 위해 분할 상환 분석 이라는 시간복잡도 계산법이 있다.

분할 상환 분석은 쉽게 말해서 시간복잡도의 평균치를 구하는 분석 방법이다.

n번 수행할때 걸리는 시간 복잡도 / n

삽입 연산(insert operation)

추가 연산(append) 는 배열의 마지막에 추가를 하는 연산이고, 삽입(insert) 는 배열의 중간에 데이터를 추가하는 연산이다.

case1. 배열에 공간이 남아있을 때

최악의 경우는 첫 번째 인덱스에 데이터를 추가하는 경우이다.

n개의 기존 데이터들을 한 칸씩 오른쪽으로 뒤로 밀기 : O(n)

첫 번째 인덱스에 삽입 : O(1)

결론 : O(n+1) => O(n)

case2. 배열에 공간이 없을 때(=꽉 찼을 때)

새로운 배열에 값을 복사 : O(n)

한 칸씩 뒤로 밀기 : O(n)

첫 번째 인덱스에 삽입 : O(1)

결론 : O(2n+1) => O(n)

삭제 연산(delete operation)

배열의 데이터를 삭제하려면, 삭제하고 싶은 인덱스보다 뒤에 있는 데이터들을 앞쪽으로 한 칸씩 당기면 된다.

case1. 맨 앞 데이터를 지울 때 (최악의 경우)

(n-1)개의 기존 데이터들을 한 칸씩 앞으로 당기기 : O(n-1)

결론 : O(n-1) => O(n)

case2. 맨 뒤 데이터를 지울 때 (최상의 경우)

데이터의 이동없이 그냥 배열의 사용 공간을 한 인덱스 줄이면 된다.

del 키워드를 쓰면 파이썬 내부적으로 알아서 데이터를 지우고, 배열 인덱스도 줄여준다. (C 정적배열과의 차이점)

결론 : O(1)