⏱️ 시간 복잡도
특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간
주요로직의 반복횟수 를 중점으로 측정된다.
어떠한 알고리즘이 주어진 입력크기를 기반으로 몇번 반복되었는가를 중점으로 설명한다.
Big-O(빅오 표기법)
복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지항을 없애서 복잡도를 나타내는 표기법
1. O(1)
입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘
스택의 Push, Pop
2. O(log₂n)
입력 데이터의 크기가 커질수록 처리 시간이 로그만큼 짧아지는 알고리즘 (10 : 2)
이진트리
3. O(n)
입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘 (1 : 1)
for 문, 재귀함수
4. O(nlog₂n)
데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘 (10 : 20)
퀵 정렬, 병합정렬, 힙 정렬
5. O(n²)
데이터가 많아질수록 처리시간이 제곱수만큼 급수적으로 늘어나는 알고리즘(10 : 100)
이중 for 문, 삽입정렬, 버블정렬, 선택정렬
6. O(2ⁿ)
데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘(10 : 1024)
피보나치 수열
🌎 공간 복잡도
특정 알고리즘이 차지하는 공간 (메모리 양)
배열이든 Map이든 Set이든 요소들을 담을 공간이면 다 적용된다.
입력크기가 1000만까지는 보통 가능하다.
하지만, 예전에 비해 컴퓨터 성능의 발달로 인해 메모리 공간이 넘쳐나다 보니 중요도는 떨어진다. 알고리즘은 시간 복잡도가 중요하다!!
🤔 공간 복잡도를 어떻게 줄일 수 있는가?
배열의 크기, 재귀 함수의 호출 횟수등을 줄인다!!
입력 크기별 적절한 시간 복잡도 선택
코딩 테스트에서 일반적인 시간 제한은 1초이며, 보통 1억(10⁸) 개 연산을 수행할 수 있다.
따라서 입력 크기 N에 따라 적절한 알고리즘을 선택해야 합니다.
| 입력 크기 (N) | 적절한 시간 복잡도 | 추천 알고리즘 |
|---|---|---|
| N <= 10 | O(N!) | 완전 탐색, 백트래킹 |
| N <= 20 | O(2^N) | 비트마스킹 DP, 외판원 문제 (TSP) |
| N <= 100 | O(N³) | 플로이드-워셜 (모든 쌍 최단 경로) |
| N <= | O(N²) | 버블 정렬, 삽입 정렬, DP, DFS, BFS |
| N <= | O(N log N) | 병합 정렬, 퀵 정렬, 이분 탐색, 세그먼트 트리 |
| N <= | O(N) or O(log N) | 선형 탐색, 해시, 투 포인터, 이분 탐색 |
