.gif&blockId=11b00c82-b138-8050-a58b-dcbceda2ef8f)
List
작업 | 예제 | 시간 복잡도 (Big-O) | 설명 |
인덱스 조회 | l[i] | O(1) | 리스트에서 인덱스 조회는 상수 시간 |
저장 | l[i] = 0 | O(1) | 리스트에 값을 저장하는 것은 상수 시간 |
길이 확인 | len(l) | O(1) | 리스트 길이를 확인하는 것은 상수 시간 |
값 추가 | l.append(5) | O(1) | 주로 상수 시간 (ICS-46에서 자세히 다룸) |
값 삭제 (끝에서) | l.pop() | O(1) | 끝에서 값을 삭제하는 것은 상수 시간 (l.pop(-1)과 동일) |
비우기 | l.clear() | O(1) | 리스트를 비우는 것은 상수 시간 (l = []과 비슷) |
슬라이싱 | l[a:b] | O(b-a) | 예: l[1:5]: O(l), l[:]: O(len(l)-0)=O(N) |
확장 | l.extend(…) | O(len(…)) | 확장하는 리스트의 길이에 따라 시간 복잡도가 결정됨 |
리스트 생성 | list(…) | O(len(…)) | 리스트의 길이에 따라 시간 복잡도가 결정됨 |
비교 (==, !=) | l1 == l2 | O(N) | 리스트를 비교할 때 O(N) 시간 소요 |
삽입 | l[a:b] = … | O(N) | 리스트에 값을 삽입할 때 O(N) 시간 소요 |
삭제 | del l[i] | O(N) | 인덱스에 따라 다르며, 최악의 경우 O(N) |
포함 여부 확인 | x in/not in l | O(N) | 리스트 내에서 값을 선형 검색 |
복사 | l.copy() | O(N) | l[:]와 동일, O(N) |
값 제거 | l.remove(…) | O(N) | 특정 값을 리스트에서 제거할 때 O(N) |
값 삭제 (특정 인덱스) | l.pop(i) | O(N) | O(N-i): 예를 들어, l.pop(0)은 O(N) |
최솟값/최댓값 | min(l)/max(l) | O(N) | 리스트를 선형으로 검색하여 최솟값 또는 최댓값을 찾음 |
역순 | l.reverse() | O(N) | 리스트를 역순으로 뒤집는 것은 O(N) |
반복 | for v in l: | O(N) | 반복문에서 return 또는 break가 없을 때 최악의 경우 O(N) |
정렬 | l.sort() | O(N log N) | key/reverse는 주로 시간 복잡도에 큰 영향을 주지 않음 |
리스트 곱셈 | k*l | O(k N) | 예: 5*l은 O(N), len(l)*l은 O(N**2) |
Set
작업 | 예제 | 시간 복잡도 (Big-O) | 설명 |
길이 확인 | len(s) | O(1) | 집합의 길이를 확인하는 것은 상수 시간 |
값 추가 | s.add(5) | O(1) | 집합에 값을 추가하는 것은 상수 시간 |
포함 여부 확인 | x in/not in s | O(1) | 리스트/튜플의 O(N)과 비교하여 집합은 상수 시간으로 값을 찾음 |
값 제거 (remove) | s.remove(..) | O(1) | 리스트/튜플의 O(N)과 비교하여 집합은 상수 시간으로 값을 제거 |
값 제거 (discard) | s.discard(..) | O(1) | 주어진 값을 제거하는 것은 상수 시간 |
값 삭제 (pop) | s.pop() | O(1) | 집합에서 임의의 값을 "무작위로" 선택하여 제거 |
비우기 | s.clear() | O(1) | 집합을 비우는 것은 상수 시간 (s = set()와 유사) |
집합 생성 | set(…) | O(len(…)) | 주어진 이터러블(iterable)의 길이에 따라 시간 복잡도가 결정됨 |
비교 (==, !=) | s != t | O(len(s)) | 두 집합을 비교할 때 O(len(s)), 길이가 다르면 O(1)로 False를 반환 |
부분집합 확인 (<=) | s <= t | O(len(s)) | s가 t의 부분집합인지 확인 (issubset) |
상위집합 확인 (>=) | s >= t | O(len(t)) | s가 t의 상위집합인지 확인 (issuperset) |
합집합 | `s | t` | O(len(s) + len(t)) |
교집합 | s & t | O(len(s) + len(t)) | 두 집합의 교집합 시간 복잡도 |
차집합 | s - t | O(len(s) + len(t)) | 두 집합의 차집합 시간 복잡도 |
대칭 차집합 | s ^ t | O(len(s) + len(t)) | 두 집합의 대칭 차집합 시간 복잡도 |
반복 | for v in s: | O(N) | 반복문에서 반환 또는 중단이 없는 경우 최악의 경우 O(N) |
복사 | s.copy() | O(N) | 집합을 복사할 때 O(N) 시간 소요 |
Dict
작업 | 예제 | 시간 복잡도 (Big-O) | 설명 |
인덱스 조회 | d[k] | O(1) | 딕셔너리에서 특정 키에 대한 값을 조회하는 것은 상수 시간 |
값 저장 | d[k] = v | O(1) | 딕셔너리의 특정 키에 값을 저장하는 것은 상수 시간 |
길이 확인 | len(d) | O(1) | 딕셔너리의 길이를 확인하는 것은 상수 시간 |
값 삭제 | del d[k] | O(1) | 딕셔너리에서 특정 키의 값을 삭제하는 것은 상수 시간 |
값 조회 (get) | d.get(k) | O(1) | 딕셔너리에서 키를 조회하거나 기본값을 반환하는 것은 상수 시간 |
값 삭제 (pop) | d.pop(k) | O(1) | 딕셔너리에서 특정 키의 값을 제거하고 반환하는 것은 상수 시간 |
항목 삭제 (popitem) | d.popitem() | O(1) | 임의로 선택된 항목을 제거하고 반환하는 것은 상수 시간 |
비우기 | d.clear() | O(1) | 딕셔너리를 비우는 것은 상수 시간 (s = {} 또는 dict()와 유사) |
뷰 반환 | d.keys() | O(1) | d.values()와 동일하게 뷰를 반환하는 것은 상수 시간 |
딕셔너리 생성 | dict(…) | O(len(…)) | 주어진 (key, value) 쌍의 개수에 따라 시간 복잡도가 결정됨 |
반복 | for k in d: | O(N) | 키, 값, 항목을 반복할 때 최악의 경우 시간 복잡도는 O(N) |
정리
•
삽입(insert,pop), 제거(delete, remove) , 탐색(check ==,≠) 포함여부 확인( catainment(in, not in))의 경우 List는 전부 O(N)이다. Set,Dict은 O(1)혹은 O(len)의 시간을 가지고 있다.
•
삽입,삭제, 탐색, 포함여부 확인등의 문제는 list보다 set,dict을 사용하는게 효율면에서 뛰어나다.
