Python 자료형(list,set,dictionary) 메서드 시간복잡도 정리

안녕하세요 ㅎㅎ

오늘은 알고리즘 문제풀이 시 가장 많이 사용하는 리스트(list), 집합(set), 딕셔너리(dictionary) 메서드의 시간 복잡도를 정리해보려 합니다. 

본격적인 시작전에 왜 여러 자료형들의 메서드에 대한 시간 복잡도를 알아야 하는지 짚고 넘어갑시다!

보통 알고리즘 문제 풀때 리스트로 큐를 구현하시는 분들이 많으실 텐데요. 여기 큐를 pop하는 반복문을 돌려서 풀어야 하는 문제가 있다고 가정해 봅시다. 만약 리스로 큐를 구현했다면 다음과 같이 나타낼 수 있는데요. 리스트의 경우 마지막 원소를 pop하는 연산의 시간 복잡도는 O(1)이지만, 그 외의 원소를 pop할 경우 원소를 한 칸씩 당기기 때문에 시간 복잡도는 O(N)이 되게 됩니다. 결국 반복문과 중첩되니 전체적인 시간 복잡도는 O(N^2)이 되는 거죠. 

q = [1,2,3,4,5,6,7,8,9,10]

for _ in range(10):
    print(q.pop(0)) 

 

시간 복잡도에서 O(N^2)은 좋지 않다는것을 다들 아실 겁니다 ㅎㅎ;;

이런 선입선출구조의 큐 같은 경우 collections 모듈의 deque를 사용하는 것이 훨씬 좋은데요. 큐를 list로 구현하지 않고 deque를 사용하여 구현하여 pop(0)를 popleft()로 대체한다면 시간 복잡도 O(N)을 O(1)로 만들 수 있습니다. 그럼 전체적인 시간 복잡도는 O(N^2)에서 O(N)이 되는 거죠. 

import collections

q = collections.deque([1,2,3,4,5,6,7,8,9,10])

for _ in range(10):
    print(q.popleft())

 

실제로 검증해보기 위해 원소 10만개를 넣고 각각 소요되는 시간을 측정해 봤습니다!

제 노트북 기준으로 리스트로 큐를 구현했을때는 1.2초가 소요되었고 deque으로 구현했을 때는 0.016초가 소요되네요. 엄청난 차이죠?? 만약 N의 개수가 훨씬 컸다면 그 차이는 훨씬 더 컸을 겁니다. 아무튼 결론은! 파이썬은 다른 언어에 비해 수행 속도가 느린 만큼 이러한 각각의 자료형 별 메서드 시간 복잡도를 잘 알아두고 대체할 수 있는 다른 자료형이나 메서드를 알아두는 것이 좋습니다. 

그럼 차근차근 알아봅시다~!

 

리스트(list)

---

 

집합(set)

---

 

딕셔너리(dictionary)

---