팔만코딩경
/
Library DB
/
Python 내장 자료구조의 시간복잡도
Search
Duplicate
Share
Python 내장 자료구조의 시간복잡도
간단소개
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
Python
Algorithm
Scrap
태그
알고리즘
9 more properties
1. List(리스트)
기본 보기
Search
List Method 시간 복잡도
이름
사용 예
시간복잡도
Index (인덱스 접근)
Open
L[i]
O(1)
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)
COUNT
21
2. Set(집합)
기본 보기
Search
Set
자료형과 메서드의 시간 복잡도
(1)
이름
사용 예
시간복잡도
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)
COUNT
16
3. Dictionary
(사전)
기본 보기
Search
Dictionary
자료형과 메서드의 시간 복잡도
(1)
이름
사용 예
시간복잡도
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)
COUNT
10