📚 List, Dict, Set 객체의 메소드별 시간 복제도 정리
일반적으로 Python이 제공하는 기능을 이용하여 소스 코드를 작성하거나 PS(Problem Solved)를 하는 경우가 많지만 시간의 복잡성을 고려하여 효율적으로 작성하면 프로그램 실행 및 코딩 테스트에서 효율성 문제에 큰 이점을 줄 수 있습니다.
그렇기 때문에 내용을 정리해 투고했습니다.
🔖 아래 표는 각 객체에 대해 (목적/예/시간 복잡도/기타) 순서로 정리되어 있습니다.
📒 List
l = list() 라고 생각한 다음의 예입니다.
|
Operation
|
예
|
Big-O
|
Notes
|
|
색인
|
l(i)
|
O(1)
|
|
|
스토어
|
l(i) = 0
|
O(1)
|
|
|
길이
|
len(l)
|
O(1)
|
|
|
Append
|
l.append(5)
|
O(1)
|
|
|
팝
|
l.pop()
|
O(1)
|
l.pop(-1)과 동일
|
|
Clear
|
l.clear()
|
O(1)
|
l = ()와 유사
|
|
Slice
|
l(a:b)
|
O(ba)
|
l(:) : O(len(l)-0) = O(N)
|
|
Extend
|
l.extend(…)
|
O(len(…))
|
확장 길이에 따라
|
|
건설
|
list(…)
|
O(len(…))
|
요소의 길이에 따라
|
|
check ==, !
= |
l1 == l2
|
O(N)
|
비교
|
|
삽입
|
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)
|
검색
|
|
복사
|
l.copy()
|
O(N)
|
l(:) 와 동일 – O(N)
|
|
팝
|
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() 라고 생각한 다음의 예입니다.
|
Operation
|
예
|
Big-O
|
Notes
|
|
색인
|
d(k)
|
O(1)
|
|
|
스토어
|
d(k) = v
|
O(1)
|
|
|
길이
|
len(d)
|
O(1)
|
|
|
Delete
|
del d(k)
|
O(1)
|
|
|
get/setdefault
|
d.method
|
O(1)
|
|
|
팝
|
d.pop(k)
|
O(1)
|
|
|
팝 아이템
|
d.popitem()
|
O(1)
|
|
|
Clear
|
d.clear()
|
O(1)
|
s = {} or = dict() 유사
|
|
보기
|
d.keys()
|
O(1)
|
d.values() 동일
|
|
건설
|
dict(…)
|
O(len(…))
|
|
|
Iteration
|
for k in d:
|
O(N)
|
|
📒 세트
s = set() 로 고려한 다음의 Example 이다.
|
Operation
|
예
|
Notes
|
Big-O
|
|
길이
|
len(s)
|
O(1)
|
집합 요소의 수
|
|
추가
|
s.add(10)
|
O(1)
|
세트에 요소 추가
|
|
Containment
|
10 in s, 10 not in s
|
O(1)
|
세트에 특정 Element가 있는지 확인
|
|
Remove
|
s.remove(10)
|
O(1)
|
세트에서 특정 요소를 삭제합니다.
|
|
디스카드
|
s.discard(10)
|
O(1)
|
세트에서 특정 요소를 삭제합니다.
|
|
팝
|
s.pop()
|
O(1)
|
세트에서 임의의 요소를 삭제합니다.
|
|
Clear
|
s.clear()
|
O(1)
|
집합을 공동 집합으로 만듭니다.
|
|
건설
|
set(…)
|
O(len(…))
|
세트 만들기
|
|
Equality
점검
|
s == t, s !
= t |
O(len(s))
|
같은 집합인지 여부 연산
|
|
서브세트
점검
|
s <= t, s >=t
|
O(len(s))
O(len
|
서브세트인지 확인
|
|
유니온
|
s|t
|
O(len(s) + len
|
일본 집합
|
|
Intersection
|
s&t
|
O(len(s) + len
|
집합
|
|
Difference
|
s – t
|
O(len(s) + len
|
차 집합
|
|
심미트릭
Diff
|
s^t
|
O(len(s) + len
|
두 세트의 상대 여집합의 합
|
|
Iteration
|
for v in s:
|
O(N)
|
세트 내의 모든 요소를 순회
|
|
복사
|
s.copy()
|
O(N)
|
세트 복사
|