[Time Complexity] Python - Find Value in List vs Set vs Dict
[시간 복잡도] 파이썬 - List vs Set vs Dict 에서 Value 찾기
| code | n = 100000 | n = 1000000 | n = 1000000 | Time Complexity |
| x in list | 0.000494 | 0.019270 |
0.235368 |
O(n) |
| list.index(x) | 0.000537 |
0.020288 |
0.246275 |
O(n) |
| for a in list: if(a==x) | 0.010289 |
0.107806 |
1.036934 |
O(n) |
| x in set | 0.000002 |
0.000002 |
0.000006 |
O(1) |
| list to set | 0.115826 |
0.066516 |
0.716471 |
|
| x in dict | 0.000005 |
0.000005 |
0.000004 | O(1) |
| list to dict | 0.147385 |
0.223651 |
2.232983 |
결론
1. Set, Dict 에서 value를 찾을 경우에 시간 복잡도 O(1)로 가장 빠름
2. 다만 List to Set/Dict conversation이 필요한 경우에 일정 값 이하의 n에서는 List를 사용
'Programming > Python' 카테고리의 다른 글
| [Time Complexity] Python - Deque vs List performance comparison (append, appendleft, pop, popleft) (2) | 2019.04.17 |
|---|---|
| [Time Complexity] Python - Numpy vs List of zeros declaration (0) | 2019.04.16 |
| 자주 쓰이는 정규식(Regular Expression) (0) | 2019.01.15 |
| python 버전 업그레이드에 의한 yum 재설치 (2) | 2018.10.29 |
| pip 설치 및 재설치 (0) | 2018.10.22 |