[파이썬] 자료형별 주요 메서드 시간복잡도 정리

여러 자료형과 빠른 시간복잡도를 가진 메스드들을 유기적으로 사용하면 코드를 짜는 시간과 동작하는 시간 모두 줄일 수 있습니다. 자료형별 많이 사용하는 메서드들을 시간복잡도와 함께 정리해 보았습니다. ⭐표시로 사용하기에 편하고 추천드리는 메서드들을 표시해보았습니다.

List 자료형 주요 메서드

대부분의 기본적인 자료구조나 순서가 중요한 자료의 경우에는 리스트 자료형을 사용합니다. $O(1)$의 시간복잡도를 가지는 append, pop을 사용하거나 인덱싱을 사용하여 요소 탐색을 진행하는 일이 일반적입니다.

in의 경우에는 list의 모든 요소를 검사하며 일치하는 요소가 있는지 찾기 때문에, list 자료형에서는 부적합할 수 있습니다. 해당 기능이 필요한 경우에는 dict나 set같은 해쉬 자료형을 추천합니다.

또한 역순과 정렬에서 원본 리스트를 변경하는 방법과 변경된 리스트를 반환하는 방법 등 2가지 방법이 존재합니다. 필요에 따라 적절히 사용하면 원본리스트를 copy하여 정렬된 리스트를 새로 만드는 등의 일을 줄일 수 있습니다.

기능	코드	시간복잡도
길이	len(my_list)	$O(1)$⭐
인덱스로 탐색	my_list[index]	$O(1)$⭐
끝에 요소추가	my_list.append(item)	$O(1)$⭐
끝에 요소뻬기	my_list.pop()	$O(1)$⭐
슬라이싱	my_list[a:b]	$O(b-a)$
리스트 연장하기	A_list.extend(B_list)	$O(len(object))$
리스트 만들기	list(my_object)	$O(len(object))$
리스트 곱하기	k*my_list	$O(k*n)$
비교하기	A_list == B_list, A_list != B_list	$O(n)$
특정요소를 탐색	item in my_list	$O(n)$
특정요소의 인덱스를 탐색	my_list.index(a)	$O(n)$
최솟값, 최댓값 찾기	min(my_list), max(my_list)	$O(n)$
역순 (⭐원본 리스트 직접 변경 & 반환값 없음)	my_list.reverse()	$O(n)$
역순 (리스트 변경 없음 & ⭐역순 리스트 반환)	reversed(my_list)	$O(n)$
정렬 (⭐원본 리스트 직접 변경 & 반환값 없음)	my_list.sort()	$O(nlogn)$
정렬 (리스트 변경 없음 & ⭐정렬 리스트 반환)	sorted(my_list)	$O(nlogn)$
특정 인덱스에 요소추가(주로 사용❌)	insert(index, element)	$O(n)$
특정 인덱스에 요소뻬기(주로 사용❌)	my_list.pop(index), del my_list[index]	$O(n)$

Dictionary 자료형 주요 메서드

해쉬 자료형을 사용하기 때문에 대부분의 값찾기가 시간복잡도 $O(1)$을 가집니다.

추천하는 메서드는 get입니다. 딕셔너리에서 기본적인 값 탐색 방법은 없는 값을 탐색할시 에러를 반환하지만, get메서드는 에러가 아닌 None을 반환합니다. 또한 해당 값이 없으면 특정한 값을 넣는 기능도 가지고 있어 잘 활용하면 코드의 길이를 확 줄일 수 있습니다.

같은 맥락으로 pop메서드 역시 추천합니다. .pop(item, default)로 키값이 없을때 삭제 과정을 진행할 때도 에러가 아닌 default값을 반환받을 수 있기 때문입니다.

또한 keys, values, items는 리스트 형태로 (key, value) 튜플을 받을 수 있는데, 신기하게도 $O(1)$로 작동합니다. for문에서 잘 활용하시면 불필요한 연산을 많이 줄일 수 있습니다.

for key, value in my_dict.items():
	print(key, value)

기능	코드	시간복잡도
길이	len(my_dict)	$O(1)$
값 찾기 (값이 없으면 에러)	my_dict[key]	$O(1)$
⭐값 찾기 (값이 없으면 None반환)	my_dict.get(key)	$O(1)$
⭐값 찾기 (값이 없으면 defualt 삽입 후 반환)	my_dict.get(key, default)	$O(1)$
⭐특정값 탐색	key in my_dict	$O(1)$
값 넣어주기/덮어쓰기	my_dict[key] = value	$O(1)$
값 삭제 (반환값 없음)	del my_list[key]	$O(1)$
⭐값 삭제 후 반환(값이 없으면 에러 반환)	my_dict.pop(key)	$O(1)$
⭐값 삭제 후 반환(값이 없으면 default 반환)	my_dict.pop(key)	$O(1)$
key값 보기	my_dict.keys()	$O(1)$⭐
value값 보기	my_dict.values()	$O(1)$⭐
⭐key, value값 보기	my_dict.items()	$O(1)$⭐
딕셔너리 만들기	dict(my_object)	$O(len(object))$

Set 자료형 주요 메서드

dict와 같이 해쉬 자료형으로써 집합 자료형이라고 불립니다. dict에서 key값만 존재한다고 생각하면 편합니다. 해쉬 자료형 답게 $O(1)$로 요소 추가시 또는 리스트에서 변경시 중복을 제거하게 됩니다. 중복을 허락하지 않아야하는 기능이나 특정 알고리즘에서 요소 탐색을 빠르게 진행해야하는 visited를 만들때 사용하면 유용합니다.

set에도 값을 삭제할 때 에러를 반환하지 않는 메서드인 discard가 존재합니다. remove보다 속도가 느리긴 하겠지만, 오류반환 없이 안정적이라는 점에서 두 메서드를 적절하게 사용하기 추천드립니다.

또한 합집합, 교집합, 차집합 등 짧은 코드로 사용가능한 굉장히 유용한 메서드들이 존재합니다. 시간복잡도는 $O(n)$입니다. (표 작성에 문제가 있어 아래 작성합니다.)

• 합집합: s1 | s2
• 교집합: s1 & s2
• 차집합: s1 - s2

기능	코드	시간복잡도
길이	len(my_set)	$O(1)$
⭐특정값 탐색	item in my_set	$O(1)$
값 넣어주기/덮어쓰기	my_set.add(item)	$O(1)$
값 삭제 (값이 없으면 에러)	my_set.remove(item)	$O(1)$
⭐값 삭제 (값이 없어도 에러 반환❌)	my_set.discard(item)	$O(1)$
셋 만들기	set(my_object)	$O(len(object))$
임의의 값 삭제 후 반환	my_set.pop()	$O(1)$