요즘 Python이 배우기도 쉽고, 알고리즘 코드를 작성할 때 짧고 생각한 그대로 표현하기에 좋은 언어이기 때문에 코딩테스트에서의 선호도가 점차 증가하고 있는 추세이다. 하지만 코드를 작성할 때, 파이썬 객체의 내장 함수를 사용하면서 해당 함수의 시간 복잡도가 얼마나 걸리는지에 대해서는 잘 알지 못하고 사용하고 있는 부분이 있어 해당 내용을 정리하고자 한다.
아래에 나오는 표는 각 객체에 대하여 내장 함수의 시간 복잡도를 정리한 표이다.
해당 표는 (목적 / 예제 / 시간복잡도 / 기타 사항) 순으로 정리하였다.
파이썬 자료형의 내장 함수 시간 복잡도 정리
List
l = list() 로 고려한 다음의 Example이다.
|
Operation
|
Example
|
Big-O
|
Notes
|
|
Index
|
l[i]
|
O(1)
|
|
|
Store
|
l[i] = 0
|
O(1)
|
|
|
Length
|
len(l)
|
O(1)
|
|
|
Append
|
l.append(5)
|
O(1)
|
|
|
Pop
|
l.pop()
|
O(1)
|
l.pop(-1) 과 동일
|
|
Clear
|
l.clear()
|
O(1)
|
l = [] 과 유사
|
|
Slice
|
l[a:b]
|
O(b-a)
|
l[:] : O(len(l)-0) = O(N)
|
|
Extend
|
l.extend(…)
|
O(len(…))
|
확장 길이에 따라
|
|
Construction
|
list(…)
|
O(len(…))
|
요소 길이에 따라
|
|
check ==, !=
|
l1 == l2
|
O(N)
|
비교
|
|
Insert
|
l.insert(i, v)
|
O(N)
|
i 위치에 v를 추가
|
|
Delete
|
del l[i]
|
O(N)
|
|
|
Remove
|
l.remove(…)
|
O(N)
|
|
|
Containment
|
x in/not in l
|
O(N)
|
검색
|
|
Copy
|
l.copy()
|
O(N)
|
l[:] 과 동일 - O(N)
|
|
Pop
|
l.pop(i)
|
O(N)
|
l.pop(0):O(N)
|
|
Extreme value
|
min(l)/max(l)
|
O(N)
|
검색
|
|
Reverse
|
l.reverse()
|
O(N)
|
그대로 반대로
|
|
Iteration
|
for v in l:
|
O(N)
|
|
|
Sort
|
l.sort()
|
O(N Log N)
|
|
|
Multiply
|
k*l
|
O(k N)
|
[1,2,3] * 3 » O(N**2)
|
Dict
d = dict() 로 고려한 다음의 Example이다.
|
Operation
|
Example
|
Big-O
|
Notes
|
|
Index
|
d[k]
|
O(1)
|
|
|
Store
|
d[k] = v
|
O(1)
|
|
|
Length
|
len(d)
|
O(1)
|
|
|
Delete
|
del d[k]
|
O(1)
|
|
|
get/setdefault
|
d.method
|
O(1)
|
|
|
Pop
|
d.pop(k)
|
O(1)
|
|
|
Pop item
|
d.popitem()
|
O(1)
|
|
|
Clear
|
d.clear()
|
O(1)
|
s = {} or = dict() 유사
|
|
View
|
d.keys()
|
O(1)
|
d.values() 동일
|
|
Construction
|
dict(…)
|
O(len(…))
|
|
|
Iteration
|
for k in d:
|
O(N)
|
|
Set
s = set()로 고려한 다음의 Example이다.
|
Operation
|
Example
|
Notes
|
Big-O
|
|
Length
|
len(s)
|
O(1)
|
집합 element들의 개수
|
|
Add
|
s.add(10)
|
O(1)
|
집합에 element 추가
|
|
Containment
|
10 in s, 10 not in s
|
O(1)
|
집합에 특정 Element가 있는지 확인
|
|
Remove
|
s.remove(10)
|
O(1)
|
집합에서 특정 Element를 제거
|
|
Discard
|
s.discard(10)
|
O(1)
|
집합에서 특정 Element를 제거
|
|
Pop
|
s.pop()
|
O(1)
|
집합에서 임의의 element하나를 제거
|
|
Clear
|
s.clear()
|
O(1)
|
집합을 공집합(empty)으로 만들어버림
|
|
Construction
|
set(...)
|
O(len(...))
|
집합을 생성
|
|
Equality
Check
|
s == t, s != t
|
O(len(s))
|
동일한 집합인지 연산
|
|
Subset
Check
|
s <= t, s >= t
|
O(len(s))
O(len(t))
|
Subset인지 여부를 확인
|
|
Union
|
s | t
|
O(len(s) + len(t))
|
합집합
|
|
Intersection
|
s & t
|
O(len(s) + len(t))
|
교집합
|
|
Difference
|
s - t
|
O(len(s) + len(t))
|
차집합
|
|
Symmetric
Diff
|
s ^ t
|
O(len(s) + len(t))
|
두 집합의 상대 여집합의 합
|
|
Iteration
|
for v in s:
|
O(N)
|
집합의 모든 element들을 순회
|
|
Copy
|
s.copy()
|
O(N)
|
집합을 복사
|
'Programing Language > Python' 카테고리의 다른 글
| 텔레그램 API 사용시 RuntimeWarning: coroutine 'Bot.get_updates' was never awaited 오류 해결방법 (0) | 2023.06.29 |
|---|---|
| 키값이나 환경변수를 관리하기 (0) | 2023.06.29 |
| 파이썬 파일 실행 할 때 생기는 __pycache__ 파일에 대해 알아보기 (0) | 2023.06.29 |
| 윈도우, 맥에서 가상환경을 구성하고 패키지 매니저 pip와 requirements.txt 로 패키지 관리하기 (0) | 2023.06.29 |
| typing module (Type annotation and Typehint) 을 통한 가독성 좋은 코드 작성하기 (0) | 2023.06.29 |
