티스토리 뷰
🌵 시간 복잡도(Time Complexity)란?
컴퓨터 과학에서 시간복잡도(Time complexity)란 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다.
일반적으로 알고리즘의 시간복잡도는 Big-O 표기법을 사용한다.
🌵 시간 복잡도가 필요한 이유는?
- 효율적인 알고리즘 구현
- 시간초과를 줄일 수 있다.
- 효율적인 알고리즘을 구현한다는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화 한다는 것이다.
- 다양한 자료형 사용
- list, set, dictionary와 같은 자료형들을 목적에 맞게 사용할 수 있다.
🌵 Big-O 표기법
Big-O 표기법은 알고리즘 효율성을 상한선 기준으로 표기한다.
즉, 최악의 경우를 고려하기 때문에 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다.
🌵 Big-O 표기법의 종류
Big-O 표기법의 종류와 간단한 예제들을 살펴보면 다음과 같다.
Big-O 표기법으로 표기할 때는 상수항을 없애야 하고, 하위 항들은 제거해야 한다.
- O(1) - stack에서 push, pop
- O(log n) - 이진트리
- O(n) - for 반복문
- O(nlog n) - 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
- O(n^2) - 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
- O(2^n) - 피보나치 수열
- O(n!)
속도는 아래로 갈 수록 느려진다.
FASTER O(1) > O(log n) > O(n) > O(nlog n) > O(n^2) > O(2^n) > O(n!) SLOWER
🌵 파이썬 자료형 별 함수들의 시간 복잡도
자료형 종류
| 자료형 | 특징 | 표현 |
| 리스트(List) | 순서 O, 수정가능 | list = [v1, v2, ...] |
| 세트(Set) | 순서 X, unique, 수정가능 | set = {v1, v2, ...} |
| 딕셔너리(Ditionary) | 순서 X, 키(immutable)-값(mutable) 맵핑 | dict = {k1:v1, k2:v2, ...} |
1. 리스트(List)의 메소드 별 시간복잡도
| Operation | Example | Big-O | Notes |
| index | list[i] | O(1) | 인덱스로 값 찾기 |
| Store | list[i] = val | O(1) | 인덱스로 데이터 저장 |
| Length | len(list) | O(1) | 리스트 길이 |
| Append | list.append(val) | O(1) | 데이터 추가 |
| Pop | list.pop() | O(1) | 마지막 데이터 pop |
| Clear | list.clear() | O(1) | 빈 리스트 |
| Slice | list[a:b] | O(b-a) | 슬라이싱 |
| Extend | list.extend(list2) | O(len(list2)) | 리스트 확장 |
| Construction | list(…) | O(len(…)) | 리스트 생성 |
| check ( ==, != ) | list1 == list2 | O(N) | |
| Insert | list[a:b] = … | O(N) | 데이터 삽입 |
| Delete | del list[i] | O(N) | 데이터 삭제 |
| Containment | x in / not in list | O(N) | x값 포함 여부 확인 |
| Copy | list.copy() | O(N) | 리스트 복제 |
| Remove | list.remove(val) | O(N) | 리스트에서 val값 제거 |
| Pop 2 | list.pop(i) | O(N) | i번째 인덱스 값 pop |
| Extreme value | min(list) / max(list) | O(N) | 전체 데이터 체크 |
| Reverse | list.reverse() | O(N) | 뒤집기 |
| Iteration | for v in list: | O(N) | 반복문 |
| Sort | list.sort() | O(N log N) | 파이썬 기본 정렬 |
| Multiply | k*list | O(k N) | 곱하기 |
2. 세트(Set)의 메소드 별 시간복잡도
| Operation | Example | Big-O | Notes |
| Add | set.add(val) | O(1) | 집합 요소 추가 |
| Containment | x in / not in set | O(1) | 포함 여부 확인 |
| Remove | set.remove(val) | O(1) | 요소 제거 (없으면 에러) |
| Discard | set.discard(val) | O(1) | 요소 제거(없어도 에러x) |
| Pop | set.pop() | O(1) | 랜덤하게 하나 pop |
| Clear | set.clear() | O(1) | |
| Construction | set(…) | O(len(…)) | |
| check ( ==, != ) | set1 != set2 | O(len(s)) | |
| <= or < | set1 <= set2 | O(len(s)) | 부분집합 여부 |
| Union | set1, set2 | O(len(s)+len(t)) | 합집합 |
| Intersection | set1 & set2 | O(len(s)+len(t)) | 교집합 |
| Difference | set1 - set2 | O(len(s)+len(t)) | 차집합 |
| Symmetric Diff | set1 ^ set2 | O(len(s)+len(t)) | 여집합 |
| Iteration | for v in set: | O(N) | 전체 요소 순회 |
| Copy | set.copy() | O(N) |
3. 딕셔너리(Dictionarty)의 메소드 별 시간복잡도
| Operation | Example | Big-O | Notes |
| Store | dict[key] = val | O(1) | 집합 요소 추가 |
| Length | len(dict) | O(1) | |
| Delete | del dict[key] | O(1) | 해당 key 제거 |
| get/set default | dict.get(key) | O(1) | key에 따른 value 확인 |
| Pop | dict.pop(key) | O(1) | key에 따른 value값 pop |
| Pop item | dict.popitem() | O(1) | 랜덤 데이터(key:value) pop |
| Clear | dict.clear() | O(1) | |
| View | dict.keys() | O(1) | key 전체 확인 |
| Values | dict.values() | O(1) | value 전체 확인 |
| Construction | dict(…) | O(len(…)) | (key, value) tuple 개수만큼 |
| Iteration | for k in d: | O(N) | 딕셔너리 전체 순회 |
🌵 관련 문제
정렬하기 문제를 통해 시간복잡도를 쉽게 이해할 수 있다.
[백준 알고리즘 2750번 : 수 정렬하기]
https://www.acmicpc.net/problem/2750
2750번: 수 정렬하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
[SOLUTION]
[백준 알고리즘 2751번 : 수 정렬하기 2]
https://www.acmicpc.net/problem/2751
2751번: 수 정렬하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
[SOLUTION]
[백준 알고리즘 10989번 : 수 정렬하기 3]
https://www.acmicpc.net/problem/10989
10989번: 수 정렬하기 3
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
www.acmicpc.net
[SOLUTION]
'🦖 Programming > Algorithm' 카테고리의 다른 글
| [Algorithm] 재귀함수(Recursive Function) , 재귀 알고리즘 (0) | 2022.09.22 |
|---|---|
| [Algorithm] 이분 탐색 / 이진 탐색 (Binary Search) 알고리즘 (2) | 2022.09.19 |
| [Algorithm] 해시를 사용한 집합(set)과 맵(map) (1) | 2022.09.16 |
| [Algorithm] 브루트 포스 알고리즘 (0) | 2022.09.07 |
| [Algorithm] 순열 및 조합 공식 정리 (0) | 2022.08.31 |