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
- DFS
- 프로그래머스
- 프로그래밍
- 파이썬
- 코딩테스트
- 딥러닝
- dp
- google coding competition
- OS
- BFS
- AI
- 그래프
- 백준
- 네트워크
- 코딩 테스트
- 동적 프로그래밍
- nlp
- CSS
- 코딩
- 동적프로그래밍
- 순열
- 구글 킥스타트
- kick start
- 운영체제
- 킥스타트
- linux
- 리눅스
- 알고리즘
- PYTHON
- 브루트포스
Archives
- Today
- Total
오뚝이개발자
[Python] 파이썬 내장함수 시간복잡도 본문
728x90
300x250
시간복잡도
아래는 자주 등장하는 시간복잡도 표기들이다. 표에서 아래로 갈수록 수행시간이 오래 걸린다.
list
리스트는 배열이다. 그렇기 때문에 사이즈가 커질수록 삽입과 삭제 연산이 비효율적으로 된다. 이럴 땐 차라리 deque를 쓰는 것이 효율적이다.
Operation |
Average |
Worst |
Copy |
O(n) |
O(n) |
Append |
O(1) |
O(1) |
Pop last |
O(1) |
O(1) |
Pop intermediate |
O(k) |
O(k) |
Get item |
O(1) |
O(1) |
Set item |
O(1) |
O(1) |
Delete item |
O(n) |
O(n) |
sort |
O(nlogn) |
O(nlogn) |
min,max |
O(n) |
O(n) |
len |
O(1) |
O(1) |
collections.deque
deque(double ended queue)는 내부적으로 doubly linked list로 구현되어 있다. 양 끝단에 접근이 가능하다. 하지만 중간 원소에 접근하는 것은 느리다.
Operation |
Average |
Worst |
Copy |
O(n) |
O(n) |
Append |
O(1) |
O(1) |
Appendleft |
O(1) |
O(1) |
Pop |
O(1) |
O(1) |
Popleft |
O(1) |
O(1) |
dict
여기서 말하는 average case는 해시함수가 충돌을 일으키지 않도록 견고하게 설계된 경우를 말한다.
Operation |
Average |
Worst |
Copy |
O(n) |
O(n) |
Get item |
O(1) |
O(n) |
Set item |
O(1) |
O(n) |
Delete item |
O(1) |
O(n) |
참고
728x90
300x250
'Language > 파이썬' 카테고리의 다른 글
[Python] list와 tuple의 차이, 사전(dictionary)과 set자료형의 가능한 key값 (0) | 2021.01.11 |
---|---|
[Python] deque 사용법 (0) | 2020.12.15 |
[Python] 파이썬 in 연산 시간복잡도 (0) | 2020.12.02 |
[Python] 파이썬 전역변수 global (0) | 2020.11.16 |
[Python] 파이썬 문자 아스키 코드 변환 (0) | 2020.11.09 |
Comments