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

emplam27·2020년 12월 28일
1

파이썬

목록 보기
3/3
post-thumbnail

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

List 자료형 주요 메서드

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

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

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

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


Dictionary 자료형 주요 메서드

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

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

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

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

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


Set 자료형 주요 메서드

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

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

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

  • 합집합: s1 | s2
  • 교집합: s1 & s2
  • 차집합: s1 - s2
기능코드시간복잡도
길이len(my_set)O(1)O(1)
특정값 탐색item in my_setO(1)O(1)
값 넣어주기/덮어쓰기my_set.add(item)O(1)O(1)
값 삭제 (값이 없으면 에러)my_set.remove(item)O(1)O(1)
값 삭제 (값이 없어도 에러 반환❌)my_set.discard(item)O(1)O(1)
셋 만들기set(my_object)O(len(object))O(len(object))
임의의 값 삭제 후 반환my_set.pop()O(1)O(1)
profile
내가 다시 보고 싶은 글이어야 남들도 보고 싶은 글이라 생각하며 작성합니다. 공부한 내용들을 건강하게 공유하며 함께 성장하고자 합니다😊😊

2개의 댓글

comment-user-thumbnail
2022년 7월 11일

잘 보고 갑니다 :)

1개의 답글