[추상 자료형] 파이썬 자료형 주요 시간 복잡도 정리

이번 포스팅에서는 파이썬 자료형들에서 많이 사용하는 연산들의 시간 복잡도를 정리해보겠습니다. 이 시간 복잡도를 바탕으로 파이썬 자료형들을 사용할 때 얼마나 효율적으로 하는지를 떠올릴 수 있을 것 같습니다.

 

리스트 (동적 배열)

연산	예시	시간복잡도
접근	list_1[0], list_1[0] = 5	O(1)
추가	list_1.append(2)	O(1) (분할 상환)
맨 뒤 삭제	list_1.pop()	O(1) (분할 상환)
길이 확인	len(list_1)	O(1)
삽입	list_1.insert(3, "성태호")	O(n)
삭제	del list_1[0], list_1.pop(3)	O(n)
탐색	"이재하" in list_1	O(n)

 

deque (더블리 링크드 리스트)

연산	예시	시간 복잡도
맨 앞 삭제	deque_1.popleft()	O(1)
맨 앞 삽입	deque_1.appendleft("김신의")	O(1)
맨 뒤 삭제	deque_1.pop()	O(1)
맨 뒤 삽입	deque_1.append("이규식")	O(1)
길이 확인	len(deque_1)	O(1)

 

딕셔너리 (해시 테이블)

연산	예시	시간복잡도
탐색	dict_1["성태호"]	O(1) (평균)
삽입	dict_1["강영훈"] = 100	O(1) (평균)
삭제	del dict_1["강영훈"], dict_1.pop("강영훈")	O(1) (평균)
길이 확인	len(dict_1)	O(1)

 

세트 (해시 테이블)

연산	예시	시간복잡도
탐색	"최지웅" in set_1	O(1) (평균)
삽입	set_1.add("손동욱")	O(1) (평균)
삭제	set_1.remove("김현승") set_1.pop("김현승")	O(1) (평균)
길이 확인	len(set_1)	O(1)

 

출처 코드잇