시간 복잡도를 구해야 하는 이유
시간 복잡도를 구해야 하는 이유는 알고리즘의 성능을 평가하고, 문제 해결에 적절한 방법을 선택하기 위해서이다. 코딩 테스트나 실무에서 알고리즘을 다룰 때, 단순히 코드가 동작하는지만 확인하는 것이 아니라 “이 코드가 얼마나 빠르게 실행될 것인가”를 고려해야 한다.
같은 문제를 해결하는 다양한 접근 방식이 존재하는데, 어떤 방법이 더 효율적인지를 판단하려면 단순 실행 시간이 아닌 입력 크기에 따른 연산 횟수 증가율을 분석해야 한다. 이를 위해 시간 복잡도를 구한다.
시간 복잡도를 구하는 이유는 크게 세 가지로 정리할 수 있다.
1. 알고리즘의 효율성을 비교하기 위해
﹒ 동일한 문제를 해결하는 여러 알고리즘이 존재할 때, 실행 속도를 객관적으로 비교해야 한다.
﹒ 실행 속도는 환경에 따라 달라질 수 있으므로, 입력 크기 증가에 따른 연산 횟수 변화를 분석하여 알고리즘의 성능을 평가한다.
2. 성능 최적화의 필요성을 판단하기 위해
﹒ 특정 문제에서 시간제한이 주어졌을 때, 알고리즘이 이를 초과하는지 예측하는 것이 중요하다.
﹒ O(N²) 알고리즘은 입력 크기가 커지면 실행 시간이 급격히 증가하지만, O(N log N) 알고리즘은 더 효율적이다.
﹒ 시간 복잡도를 분석하면 비효율적인 알고리즘을 개선하고 최적화할 필요성을 판단할 수 있다.
3. 대략적인 실행 시간을 예측하기 위해
﹒ 실제 실행 시간을 직접 측정하는 것은 환경적인 요인에 의해 변동될 수 있지만, 시간 복잡도를 통해 대략적인 성능을 예측할 수 있다.
﹒ O(1) 알고리즘은 즉시 실행되지만, O(N²) 알고리즘은 입력 크기가 커질수록 실행 시간이 급격히 증가한다.
﹒ 이러한 차이를 이해하면 문제 해결에 적절한 알고리즘을 선택하는 데 도움이 된다.
결국, 시간 복잡도를 구하는 것은 실행 가능성을 예측하고, 알고리즘의 성능을 비교하며, 최적화가 필요한지를 판단하기 위해 필수적인 과정이다. 이를 통해 우리는 더 빠르고 효율적인 알고리즘을 선택하고, 문제 해결에 적절한 전략을 수립할 수 있다.
시간 복잡도를 나타내는 방법
시간 복잡도는 알고리즘이 입력 크기 N에 따라 실행되는 연산 횟수를 표현하는 지표이다. 보통 최악의 경우를 고려하여 빅오 표기법(Big-O)으로 나타낸다.
﹒ 최상의 경우: 오메가 표기법 (Big-Ω Notation)
﹒ 평균의 경우: 세타 표기법 (Big-θ Notation)
﹒ 최악의 경우: 빅오 표기법 (Big-O Notation)
평균적인 경우를 평가할 수 있는 세타 표기법이 있지만, 복잡성이 크고 평가가 까다롭기 때문에 시간 복잡도는 최악의 경우를 기준으로 하는 빅오 표기법으로 판단한다. 빅오 표기법의 복잡성은 시간 복잡도와 공간 복잡도로 나뉜다.
﹒ 시간 복잡도: 입력 크기 N에 따라 연산 횟수가 어떻게 변하는지를 분석하여 최적의 알고리즘을 선택한다.
﹒ 공간 복잡도: 입력 크기에 따라 추가적인 메모리를 얼마나 사용하는지를 분석하여 최적화할 수 있다.
[ 대표적인 시간 복잡도 및 알고리즘 예시 ]
| 표기법 | 설명 | 대표적인 알고리즘 |
| O(1) | 입력 크기에 관계없이 일정한 시간이 걸리는 알고리즘 | 배열 인덱스 접근, 해시 테이블 조회 |
| O(log N) | 입력 크기가 커질수록 실행 시간이 느리게 증가하는 알고리즘 | 이진 탐색, AVL 트리 삽입 및 삭제 |
| O(N) | 입력 크기에 비례하여 실행 시간이 증가하는 알고리즘 | 선형 탐색, 단순 반복문 |
| O(N log N) | 대부분의 효율적인 정렬 알고리즘 | 병합 정렬, 퀵 정렬 |
| O(N²) | 이중 반복문을 포함하는 알고리즘 | 버블 정렬, 선택 정렬 |
| O(2ˆN) | 입력 크기가 커질수록 실행 시간이 기하급수적으로 증가하는 알고리즘 | 피보나치 수열 (재귀적 구현) |
| O(N!) | 모든 경우의 수를 고려하는 완전 탐색 방식 | 순열 생성, 외판원 문제(TSP) |
[ 자료구조의 시간 복잡도 비교 ]
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
| 배열, Array | O(1) | O(N) | O(N) | O(N) |
| 스택, Stack | O(N) | O(N) | O(1) | O(1) |
| 큐, Queue | O(N) | O(N) | O(1) | O(1) |
| 해시 테이블, Hash Table | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리, BST | O(log N) | O(log N) | O(log N) | O(log N) |
| 힙, Heap | O(N) | O(log N) | O(log N) | O(log N) |
[ 정렬 알고리즘의 시간 복잡도 비교 ]
| 알고리즘 유형 | 최선의 경우 | 평균의 경우 | 최악의 경우 |
| 버블 정렬, Bubble Sort | O(N) | O(N²) | O(N²) |
| 선택 정렬, Selection Sort | O(N²) | O(N²) | O(N²) |
| 삽입 정렬, Insertion Sort | O(N) | O(N²) | O(N²) |
| 병합 정렬, Merge Sort | O(N log N) | O(N log N) | O(N log N) |
| 퀵 정렬, Quick Sort | O(N log N) | O(N log N) | O(N²) |
| 힙 정렬, Heap Sort | O(N log N) | O(N log N) | O(N log N) |
| 이진 탐색, Binary Search | O(1) | O(log N) | O(log N) |