시간 복잡도를 알아야 하는 이유
백준에서 알고리즘을 풀다 보니 '시간 초과'되는 경우를 자주 겪었습니다. 문제를 풀고 나서도 결과 시간이 다른 사람들보다 상당히 높게 나오는 경우가 있었는데요. 확실히 파이썬 연산자들의 시간 복잡도(Big-O)를 정확히 알고 있어야 한다는 필요성을 느꼈습니다. 이번 포스팅을 통해서 파이썬 자료형들과 자료형에 따른 연산자, 메서드에 따른 시간 복잡도가 얼마나 걸리는지 알아보겠습니다.
시간 복잡도
계산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 컴퓨터과학에서 알고리즘의 시간 복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오(Big-O)표기법을 사용하여 나타낸다. reference 위키백과
시간복잡도 = 한마디로 시간이 얼마나 걸리느냐
파이썬의 기본 산술 연산들은 O(1)으로 즉각적인 결과가 나타납니다.
길이가 n인 리스트를 처음부터 끝까지 요소를 하나씩 출력한다면, print함수를 n번 사용하므로 O(1) x n이므로 O(n)이라고 생각할 수 있습니다. 이중 for문은 O(n²), 삼중 for문은 O(n³)과 같은 방식으로 진행됩니다.
- 복잡한 정도
n의 차수가 높아질수록 시간 복잡도가 올라가고 그만큼 시간이 오래 걸린다고 생각하면 됩니다. 전체적인 test case가 적으면 문제가 안됩니다. 하지만 n이 100,000 이상이나 가끔 백만 이상의 값들이 들어갈 경우 n의 차수에 따라서 걸리는 시간이 아주 급격하게 증가합니다.
출처 : https://debugdaldal.tistory.com/158
자료형에 따른 시간 복잡도
각 자료형과 해당 메서드, 연산자에 따른 시간 복잡도가 얼마나 되는지 알아보겠습니다. 각 자료형의 구성과 동작이 어떻게 돌아가는지 생각해보면 쉽게 시간 복잡도를 유추할 수 있습니다. 각 자료형이 어떻게 동작하는지 생각하면서 아래의 표를 보시면 쉽게 이해하실 수 있을 것입니다.
리스트 자료형과 메서드의 시간 복잡도
집합(set) 자료형과 메소드의 시간 복잡도
딕셔너리(Dictionary) 자료형과 메소드의 시간 복잡도
자료형에 따른 시간 복잡도 비교
메서드들의 시간 복잡도가 다르기 때문에 필요에 따라서 어떤 자료형을 사용하는 것이 좋은지 생각하면 더욱 좋은 알고리즘으로 파이썬 코드를 작성하실 수 있을 것입니다.
List 자료형은 삽입, 제거, 탐색, 포함 여부 확인 모두 O(n)에 해당하는 시간 복잡도를 가지고 있습니다.
Set과 Dictionary는 삽입, 제거, 탐색, 포함여부확인 연산에 O(1)의 시간 복잡도를 가지고 있습니다.
탐색과 확인이 주로 필요한 연산이라면 Set이나 Dictionary를 사용하는 것이 좋고 순서와 index에 따른 접근이 필요하다면 List 자료형을 사용하는 것이 좋을 것입니다.
추가 참고자료 :
Heapq의 시간복잡도:
heapq.heapify = O(n)
heapq.heappop, heapq.heappush = O(logn)
참고자료
- Reference : https://chancoding.tistory.com/43
'알고리즘 문제 > CP코드 저장소' 카테고리의 다른 글
Trie (0) | 2023.01.18 |
---|---|
Combinations (0) | 2023.01.02 |
List 값들의 정렬 (2차원 배열 / 길이) (0) | 2022.12.31 |
RoundUp (0) | 2022.12.30 |
Binary Search (0) | 2022.12.29 |