300x250
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- OS
- 프로그래머스
- DFS
- kick start
- 코딩
- 그래프
- 백준
- google coding competition
- CSS
- AI
- 네트워크
- 파이썬
- 코딩 테스트
- 운영체제
- nlp
- 딥러닝
- 리눅스
- 동적 프로그래밍
- PYTHON
- 코딩테스트
- 알고리즘
- linux
- 순열
- dp
- 브루트포스
- 킥스타트
- 구글 킥스타트
- 동적프로그래밍
- BFS
- 프로그래밍
Archives
- Today
- Total
오뚝이개발자
[Python] 파이썬 in 연산 시간복잡도 본문
728x90
300x250
파이썬에는 in 연산자가 있다. 보통 리스트, 튜플, 집합, 딕셔너리 같이 연속적인 자료구조에 속한 멤버를 확인하거나 순회할 때 사용한다. 그렇다면 in 연산자의 시간복잡도는 어떻게 될까?
List
l = [1, 2, 3, 4, 5]
# 멤버 확인
if 1 in l :
print("1 is in l")
# 순회
for i in l :
print(i)
Tuple
t = (1, 2, 3, 4, 5)
# 멤버 확인
if 1 in t :
print("1 is in t")
# 순회
for i in t :
print(i)
Set
s = {1, 2, 3, 4, 5}
# 멤버 확인
if 1 in s :
print("1 is in s")
# 순회
for i in s :
print(i)
Dictionary
d = {1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e'}
# 멤버 확인
if 1 in d.keys() :
print("1 is in d keys")
# 순회
for i in d.items() :
print(i)
시간복잡도
핵심은 각 자료구조마다 in을 사용할 때 시간복잡도가 다르다는 것이다.
list, tuple
- Average : O(n)
- 하나하나 순회하기 때문에 O(n)만큼의 시간복잡도를 갖는다
set, dictionary
- Average : O(1), Worst : O(n)
- 내부적으로 hash를 통해 저장하므로 접근하는 시간은 O(1)이다. 하지만 해쉬의 충돌이 많아 성능이 떨어지는 경우 O(n)이 걸릴 수도 있다.
참고자료
twpower.github.io/120-python-in-operator-time-complexity
728x90
300x250
'Language > 파이썬' 카테고리의 다른 글
[Python] deque 사용법 (0) | 2020.12.15 |
---|---|
[Python] 파이썬 내장함수 시간복잡도 (0) | 2020.12.15 |
[Python] 파이썬 전역변수 global (0) | 2020.11.16 |
[Python] 파이썬 문자 아스키 코드 변환 (0) | 2020.11.09 |
[Python] 파이썬 heap(heapq 모듈) (0) | 2020.10.29 |
Comments