[Python] 파이썬 자료형별 주요 연산자의 시간복잡도(Big-O)

hwwwa·2022년 6월 20일
0

🐼 Python

목록 보기
17/18
post-custom-banner

참고자료: Complexity of Python Operations

List

OperationExampleBig-ONotes
Indexl[i]O(1)
Storel[i] = 0O(1)
Lengthlen(l)O(1)
Appendl.append(5)O(1)
Popl.pop()O(1)l.pop(-1) 과 동일
Clearl.clear()O(1)l = [] 과 유사
Slicel[a:b]O(b-a)l[:] → O(N)
Extendl.extend(…)O(len(…)확장 길이에 따라
Constructionlist(…)O(len(…)요소 길이에 따라
check ==, !=l1 == l2O(N)비교
Insertl.insert(i, v)O(N)i 위치에 v를 추가
Deletedel l[i]O(N)
Removel.remove(…)O(N)
Containmentx in/not in lO(N)검색
Copyl.copy()O(N)l[:]과 동일
Popl.pop(i)O(N)l.pop(0) → O(N)
Extreme valuemin(l) / max(l)O(N)검색
Reversel.reverse()O(N)
Iterationfor v in l:O(N)
Sortl.sort()O(NlogN)
Multiplyk*lO(kN)[1,2,3] * 3 → O(N**2)

Set

OperationExampleBig-ONotes
Lengthlen(s)O(1)
Adds.add(5)O(1)
Containmentx in/not in sO(1)list와 tuple에서는 O(N)
Removes.remove(…)O(1)list와 tuple에서는 O(N)
Discards.discard(…)O(1)
Pops.pop()O(1)pop되는 value는 랜덤
Clears.clear()O(1)s = set() 과 유사
Constructionset(…)O(len(…))요소 길이에 따라
check ==, !=s != tO(len(s))len(t)와 같음. 두 set의 길이가 다르면 O(1)
<= / <s <= tO(len(s))issubset()
>= / >s >= tO(len(t))issuperset() s<=t==t>=s
UnionstO(len(s)+len(t))
Intersections & tO(len(s)+len(t))
Differences - tO(len(s)+len(t))
Symmetric Diffs ^ tO(len(s)+len(t))
Iterationfor v in s:O(N)
Copys.copy()O(N)

Dict

OperationExampleBig-ONotes
Indexd[k]O(1)
Stored[k] = vO(1)
Lengthlen(d)O(1)
Deletedel d[k]O(1)
Get/setdefaultd.methodO(1)
Popd.pop(k)O(1)
Pop itemd.popitem()O(1)pop되는 item은 랜덤
Cleard.clear()O(1)s = {} / dict() 와 유사
Viewd.keys()O(1)d.values() 와 동일
Constructiondict(…)O(len(…))요소 길이에 따라
Iterationfor k in d:O(N)
post-custom-banner

0개의 댓글