[Algorithm] - List 주요 연산 시간복잡도
List자료형은 순서대로 저장하는 시퀀스이자 변경 가능한 목록(Mutable List)를 말한다. 입력 순서가 유지되며, 내부적으로는 동적 배열로 구현되어 있다. Python에서 배열의 역할을 하는 자료형이다.
List의 주요 특징
- Stack과 Queue를 동시에 구현할 수 있다.
- Stack과 Queue에서 사용 가능한 모든 연산을 함께 제공
- O(1)의 연산속도를 가지는 다양한 연산이 있다.(append(), Pop() 등)
- 요소를 삭제하거나 큐의 연산이기도 한 첫 번째 요소를 추출하는 경우(pop(0)) 시간복도는 O(n)이다.
- Linked List에 대한 포인트 목록을 배열 형태로 관리하고 있는 것과 같음(배열 + 연결 리스트)
- 연결 리스트에 대한 포인터 목록을 관리하고 있기 때문에 다양한 타입이 동시에 사용될 수 있음([‘1’, ‘안녕’])
List의 주요 연산 시간복잡도 아래와 같다.
주요 연산 시간복잡도
| 순서 | 연산 | 예시 | 시간 복잡도 | 설명 |
|---|---|---|---|---|
| 1 | Index | a[i] | O(1) | 인덱스로 값 찾기 |
| 2 | Store | a[i] = 0 | O(1) | 인덱스로 데이터 저장 |
| 3 | Length | len(a) | O(1) | 리스트 길이 |
| 4 | Append | a.append(5) | O(1) | 리스드 뒤에 데이터 저장 |
| 5 | Pop | a.pop() | O(1) | 가장 뒤의 데이터 pop |
| 6 | Clear | a.clear() | O(1) | a = [] |
| 7 | Slice | a[a:b] | O(k) | 슬라이싱되는 요소들 수 만큼 비례 |
| 8 | Extend | a.extend(…) | O(k) | 확장되는 길이만큼 |
| 9 | Construction | list(…) | O(k) | 리스트 길이만큼 |
| 10 | check ==, != | a1 == a2 | O(N) | 전체 리스트가 동일한지 확인 |
| 11 | Insert | a[a:b] = … | O(N) | 데이터 삽입 |
| 12 | Delete | del a[i] | O(N) | 데이터 삭제ㅣ |
| 13 | Containment | x in/not in a | O(N) | 포함 여부 확인 |
| 14 | Copy | a.copy() | O(N) | 복제 |
| 15 | Remove | a.remove(…) | O(N) | 제거 |
| 16 | Pop | a.pop(i) | O(N) | 제거된 값 이후를 전부 한칸씩 당겨줘야함 |
| 17 | Extreme | value min(a)/max(a) | O(N) | 전체 데이터를 확인해야함 |
| 18 | Reverse | a.reverse() | O(N) | 뒤집기 |
| 19 | Iteration | for v in a: | O(N) | 전체 데이터 확인하므로 |
| 20 | Sort | a.sort() | O(N Log N) | 파이썬 기본 정렬 알고리즘(Timsort 알고리즘) |
| 21 | Multiply | k*a | O(k N) | 리스트의 곱은 리스트 개수 늘어남 |