효율성
-
[Python] List와 Set에서의 in 연산자 성능 비교하기.개발 공부/Python 2021. 6. 22. 15:21
in 연산자를 쓸 때는 set으로 바꿔서 쓰면 빠르다. List에서 in 연산자를 사용하면 사실 상 for문을 한번 도는 것이기 때문에 선형 시간인 O(n)의 시간 복잡도를 가집니다. 제 주변에서 이를 모르고 사용하다가 알고리즘 문제에서 Timeout이 걸리는 경우를 종종 보았는데, List에서 set으로 바꾸고 in 연산을 하면 이러한 부담이 많이 줄어들게 됩니다. List 자료형에서는 in 연산자의 시간 복잡도는 O(n)입니다. a = list(range(1, 10000001)) print(1 in a) # 첫번째 값 print(10000000 in a) # 마지막 값 0.17809176445007324 0.45179247856140137 그래서 1 ~ 10,000,000의 값을 가진 리스트에서 맨 ..