Python 자료형 별 주요 연산자의 TimeComplexity (Big - O)

nathan·2021년 3월 14일
0

Python

목록 보기
1/7
post-thumbnail

알고리즘 문제를 풀면서 TimeComplexity에 대해 자료형 별로 다르다는 것을 알게 되었다.

그래서 이번엔 파이썬의 다양한 자료형 별로 주요 연산자의 TimeComplexity를 비교해 보고자 한다.

(해당 내용은 초보몽키님의 개발공부로그를 참고하였다.)

List

OperationExampleBig-ONotes
IndexList[i]O(1)-
StoreList[i] = "a"O(1)-
Lengthlen(List)O(1)-
AppendList.append("a")O(1)1개의 원소로 넣음
PopList.pop()O(1)List.pop(-1)과 동일
마지막 인덱스의 element를 pop
PopList.pop(i)O(N)index를 찾아 element를 pop
ClearList.clear()O(1)List=[]과 유사
SliceList[k:n]O(n-k)List[:] : O(len(List)-0
= O(N)
ExtendList.extend(...)O(len(...))확장 길이에 따라 다름
리스트 형태로 넣으면,
원소들이 차례로 들어가기 때문
ConstructionList(...)O(len(...))생성 길이에 따라 다름
check ==, !=List_1 == List_2O(N)비교
InsertList.insert(index, value)O(N)index를 찾아 value를 추가
Deletedel [i]O(N)index를 찾고난 후 삭제
pop과 달리 리스트의 구간 삭제 가능
RemoveList.remove(...)O(N)인덱스가 아닌 값을 입력하는 방식
(pop, del과 다름)
Containmentx in/not in ListO(N)검색
CopyList.copy()O(N)List[:]와 동일함
Extreme valuemin(List), max(List)O(N)검색
ReserveList.reverse()O(N)반대로 정렬
Iterationfor v in List:O(N)반복
SortList.sort()O(N*logN)-
Multiplyk*ListO(k*N)-

Dict

키와 값을 갖는 데이터 구조
키는 내부적으로 hash 값으로 저장
순서를 따지지 않는다. 즉, 인덱스가 없다.

  • (참고)
    • 집합은 키를 변경할 수 없음
    • iteration 도중 size가 바뀌어선 안됨
    • value로 key 값을 찾아낼 수는 없음
OperationExampleBig-ONotes
Indexd[k]O(1)-
Stored[k] = vO(1)-
Lengthlen(d)O(1)-
Deletedel d[k]O(1)-
get/set defaultd.methodO(1)-
Popd.pop(k)O(1)-
Pop itemd.popitem()O(1)-
Cleard.clearO(1)s = {} or = dict() 유사
Viewd.keys()O(1)d.values()와 동일
Constructiondict(...)O(len(...))-
Iterationfor k in d:O(N)-

Set

중복을 허용하지 않고 순서가 없다(Unordered).
리스트나 튜플은 순서가 있기(ordered) 때문에 인덱싱을 통해 자료형의 값을 얻을 수 있지만,
set 자료형은 순서가 없기(unordered) 때문에 인덱싱으로 값을 얻을 수 없다. 이는 딕셔너리와 비슷하다.

만약 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)similar to s = set()
Constructionset(...)O(len(....))depends on length
check ==, !=s != tO(len(s))len(t)와 같음.
두 집합의 길이가 다르면 False 반환 - O(1)
Iterationfor v in s:O(N)Worst: no return/break in loop
Copys.copy()O(N)-

Reference

profile
나는 날마다 모든 면에서 점점 더 나아지고 있다.

0개의 댓글