[파이썬 자료구조] List

List 자료구조에 대한 내용입니다.

자료구조로서의 리스트는 자료들의 덩어리입니다.

그리고 자료들 사이에 순서가 존재합니다

이러한 순서에 접근하기 위해서 인덱싱을 사용합니다.

리스트연산

1.삽입

append()를 사용해서 리스트에 값을 추가할 수 있습니다.

2.삭제

pop()을 사용해서 삭제가 가능합니다.

시간복잡도

삽입, 삭제 시에는 O(n)의 시간복잡도를 가집니다.

그렇다면 어떻게 시간복잡도를 줄여서 성능을 올릴 수 있을까요?

c언어에서는 충분한 배열의 크기를 선언해서 사용합니다.

반면 파이썬은 삽입,삭제하면서 리스트의 메모리공간이 변합니다. 

그렇다면 어떻게 메모리를 변화시킬까요?

1. 삽입할때마다 메모리를 일정한 크기씩 확장하는 방법

메모리가 부족할때마다 2씩 메모리를 확장.

k = n/c

T(n) = n + c + 2c + … + kc = n + c(1+2+ … + k) = n + ck(k+1)/2

T(n)~O(n+k2)~O(n2)

시간복잡도는 O(n)이 됩니다.

2. 할당된 크기게 비례하게 크기를 확장

메모리가 부족할때마다 2의 제곱으로 메모리를 확장하는 방법입니다.

T(n) = n + 1 + 2 + 4 + … + 2^k = n + 2k+1 – 1 = 3n -1

삽입의 평균시간복잡도는 O(1)