[Python] - List, Set, Dict 시간 복잡도(Big-O)

알고리즘의 시간복잡도는 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 
알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법으로 표현할 때, 시간복잡도를 점근적으로 묘사한다고 말한다. 

 

ex)  약 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 (어떤 n0보다 크지 않은 모든 n에 대하여) 5n^3 + 3n의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n^3)이라고 할 수 있다.

 

---

List

---

Set

 

 

---

Dictionary

 

참고자료
https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

 

---

List와 Set의 탐색 속도 차이
두 방식 모두 안에 요소가 포함되어 있는지 여부를 알 수 있는 in 연산자를 사용할 수 있다.
여기서 Set의 속도가 더 빠르다.
List는 in연산자를 사용하면 for문을 한번 도는 것과 같다( O(n) ).
Set은 in 연산자를 사용시 복잡도가 O(1)이다.
딕셔너리의 키를 탐색하는 in 역시 set과 동일한 시간복잡도를 가진다.