Search
Duplicate

Python 내장 자료구조의 시간복잡도

간단소개
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
Python
Algorithm
태그
알고리즘
Scrap
8 more properties

1. List(리스트)

기본 보기
Search
이름
사용 예
시간복잡도
Store (대입 연산)
Open
L[i] = 0
O(1)
Length (len함수)
Open
len(L)
O(1)
Append (요소 추가)
Open
L.append(5)
O(1)
Pop (마지막 요소 꺼내기)
Open
L.pop()
O(1)
Clear (요소 모두 제거)
Open
L.clear()
O(1)
Slice (슬라이싱)
Open
L[a:b]
O(b-a)
Extend (리스트 확장)
Open
L.extend()
O(len(...))
Construction (리스트 변환)
Open
list(...)
O(len(...))
Check (리스트 비교 연산)
Open
L1 == L2
O(N)
Insert (데이터 삽입)
Open
L[a:b]=...
O(N)
Delete (데이터 삭제)
Open
del L[i]
O(N)
Containment (포함 여부 확인)
Open
x in / not in L
O(N)
Copy (리스트 복사)
Open
L.copy()
O(N)
Remove (요소 제거)
Open
L.remove(...)
O(N)
Pop (특정 위치 요소 꺼내기)
Open
L.pop(i)
O(N)
Extreme Value (최대 최소 구하기)
Open
min(L)/max(L)
O(N)
Reverse (역순)
Open
L.reverse()
O(N)
Iteration (반복문)
Open
for v in L:
O(N)
Sort (정렬)
Open
L.sort()
O(N Log N)
Multiply (리스트의 곱셈)
Open
k*L
O(k N)
COUNT21

2. Set(집합)

기본 보기
Search
이름
사용 예
시간복잡도
Add (요소 추가)
Open
s.add(5)
O(1)
Containment (포함 여부 확인)
Open
x in/not in s
O(1)
Remove (요소 제거)
Open
s.remove(..)
O(1)
Discard (특정 요소 제거)
Open
s.discard(..)
O(1)
Pop (랜덤 삭제)
Open
s.pop()
O(1)
Clear (요소 모두 제거)
Open
s.clear()
O(1)
Construction (Set 변환)
Open
set(...)
O(len(...))
check ==, != (전체 요소 동일 여부 확인)
Open
s != t
O(len(s))
<=/< (부분집합 확인)
Open
s <= t
O(len(s))
>=/> (부분집합 확인)
Open
s >= t
O(len(t))
Union (합집합)
Open
s, t
O(len(s)+len(t))
Intersection (교집합)
Open
s & t
O(len(s)+len(t))
Difference (차집합)
Open
s - t
O(len(s)+len(t))
Symmetric Diff (여집합)
Open
s ^ t
O(len(s)+len(t))
Iteration (반복문)
Open
for v in s:
O(N)
Copy (복제)
Open
s.copy()
O(N)
COUNT16

3. Dictionary (사전)

기본 보기
Search
이름
사용 예
시간복잡도
Store (데이터 저장)
Open
d[k] = v
O(1)
Length (길이 출력)
Open
len(d)
O(1)
Delete (요소 제거)
Open
del d[k]
O(1)
get/setdefault (key에 따른 value 확인)
Open
d.get(k)
O(1)
Pop (요소 제거)
Open
d.pop(k)
O(1)
Pop item (랜덤하게 요소 제거)
Open
d.popitem()
O(1)
Clear (요소 모두 제거)
Open
d.clear()
O(1)
View (키값 전체 확인)
Open
d.keys()
O(1)
Construction (Dictionary 변환)
Open
dict(...)
O(len(...))
Iteration (반복문)
Open
for k in d:
O(N)
COUNT10