[파이썬 - 알쓸신잡] 왜 Dict는 List 보다 빠를까?

 

항상 코테 문제를 풀거나 시스템을 구성할때 고려되어야할 중요한 포인트가 있다

바로 `시간 복잡도`이다 

 

가끔 쉬워보이는 문제도 시간복잡도와 마주치게 되면 꽤 어려워진다

오늘은 이런 시간복잡도에 대한 이야기를 나눠보려고 한다

 

속도의 한계를 보여주지!

그렇다면 시간 복잡도가 가장빠른 경우는 어떠한 상황일까

당연히 O(1)인 상황이다

 

모든 결과가 한번에 처리되고 출력되는 속도이다

우리가 처리해야하는 데이터의 길이가 n이는 n+1이든 m이든 상관없이 O(1)이면 매우 빠르다

 

아직 이해가 되지 않을 수 있다

예시를 들어서 이해해보자

 

대표적으로 우리가 n개의 배열을 하나씩 print 하게 되면 얼마의 시간 복잡도가 걸릴까?

당연히 O(1)이면 매우 최적이겠지만

O(n) 만큼의 시간 복잡도가 소요된다

 

즉, 하나를 출력하는데 O(1) x n번 반복되기 때문에 O(n)이 걸리는 것이다

 

이를 응용해 본다면 위 배열을 이중for문으로 출력하면 O(n**2), 삼중 for문의 경우 O(n**3)

즉, n배씩 증가한다

 

따라서 처리해야하는 값의 길이가 늘어남에 따라서 어떠한 방식으로 문제를 처리하느냐는 

시간복잡도에 배우 큰 영향을 미치게 된다

시간복잡도의 크기

따라서 우리는 O(log(n)) 정도의 시간에 맞추면 매우 효율적인 방법이라고 할 수 있다

사실상 O(1)는 불가능하기 때문이다

---

자료형에 따른 시간 복잡도

물론 처리해야할 데이터의 길이 뿐만 아니라 

사용하는 자료형에 따라서 시간 복잡도가 달라지기도 한다

 

아래에는 Python의 List, Set, Dict 의 시간 복잡도를 표로 정리한 내용이 나와있다

 

1. List

List

2. Set

 

3. Dict

 

특히, 신기한 부분은 List와 Dict를 비교해보면 특정 요소를 삭제할 때 Dict의 경우 O(1)이 걸리고 List의 경우 O(n)이 걸리는 것을 알 수 있다

 

그리고 대부분의 기능이 Dict가 List 보다 빠르다는 것을 확인할  수있다

 

왜이런 차이가 발생할까??

Set, Dict의 자료구조가 검색이 빠른 이유? hash 함수

바로 Dict와 Set은 해쉬 테이블이라는 것을 이용하기 때문이다

List 처럼 배열의 순서를 돌면서 탐색하는 것이 아니라

해당 값의 고유값이라고 할 수 있는 해쉬 값을 알고 있으면 바로 접근할 수 있는 것이다

따라서 List와 비교를 했을때 빠른 탐색 결과를 보여준다

 

따라서 순서를 다루는 문제를 활용핼때는 List와 같은 배열 계열을 활용하는 것이 편하고

탐색 같은 경우에는 Dict나 Set 같은 자료구조를 이용하는 것이 시간복잡도 측면에서 좋을 것이다