시간 복잡도란?
알고리즘을 공부하다 보면 '시간 복잡도' 라는 개념을 반드시 마주치게 된다. 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수이다. 1억 번의 연산을 1초의 시간으로 간주한다. 즉, 특정 알고리즘이 주어진 문제를 해결하느 데 걸리는 시간을 입력 데이터의 크기(n) 에 대한 함수로 표현한 것이다.
ex) 제한시간 2초 : 2억연산 안에 답 도출
입력 데이터가 늘어날 때 알고리즘의 실행 시간이 얼마나 오래 걸리는지를 나타내는 척도이다. 좋은 코드는 기능 동작을 넘어, 효율적으로 동작하는 코드를 만드는 것이다. 이 '효율성'을 객관적으로 측정하는 핵심 지표가 시간 복잡도이다.
백준 문제를 풀 때 흔히 나오는 시간 초과와 시간 복잡도를 연관하여 생각하면 된다. 데이터 100 개를 처리할 때는 두 알고리즘의 속도 차이가 미미할 수 있다. 하지만 100만 개, 1억 개의 데이터를 처리해야 한다면 시간 복잡도에 따라 실행 시간은 수백 배까지 차이날 수 있다. 따라서 시간 복잡도 개념에 대한 이해는 필수적이다.
시간 복잡도 유형
1. 빅-오메가
최선의 경우 얼마나 빠른가? (성능 하한선)
최선일 때의 연산 횟수이다.
2. 빅-세타
평균적으로 얼마나 걸리는가? (평균 실행 시간)
보통일 때 연산 횟수, 평균적인 값을 구한다.
N/2 정도의 연산 횟수를 가진다.
3. 빅-오 (Big O)
최악의 경우 얼마나 오래 걸리는가? (성능 상한선)
시간 복잡도를 표현할 때는 주로 빅오(Big-O) 표기법을 사용한다. 입력 데이터의 크기(n)가 무한대로 커질 때, 함수의 실행 시간이 어떤 형태로 증가하는지를 나타내는 점근적 표기법 중 하나이다. 최악일 때의 연산 횟수를 나타낸 표기법으로, 모든 경우를 가정하는 표기법이다.
알고리즘의 실행 시간에서 가장 큰 영향력을 가진 항만을 남기고, 계수는 무시하여 성능의 대략적인 추세를 나타내는 방식이다. 예를 들어 아래와 같은 알고리즘이 있다면 가장 큰 영향을 주는 항만을 남겨, 시간 복잡도는 O(n^2) 이라 판단한다.
3n² + 5n + 10 => n²
코딩 테스트 시, 최악의 횟수를 염두에 두고 코딩 테스트에 임해야 한다. > 코딩 테스트 시 빅-오 를 사용해야한다 !
연산 횟수 계산 방법
연산 횟수 = 알고리즘 시간 복잡도 X 데이터의 크기
주어진 데이터의 크기를 확인해서, 연산 횟수를 구하는 것이 중요하다.
주요 시간 복잡도 유형별 예시
- 상수 시간 (Constant Time)
입력 데이터의 크기(n)와 상관없이 실행 시간이 일정한 알고리즘이다. 가장 빠른 시간 복잡도이다.
// 배열의 특정 인덱스에 접근하여 값을 반환하는 메서드
public int getValue(int[] arr, int index) {
// 배열의 크기나 인덱스 위치에 상관없이 한 번의 연산으로 값을 찾는다.
return arr[index];
}
- 선형 시간 (Linear Time)
입력 데이터의 크기(n)에 비례하여 실행 시간이 증가하는 알고리즘이다. for 반복문이 한 번 사용되는 경우가 대표적이다.
// 배열의 모든 요소를 합산하여 반환하는 메서드
public int sumAll(int[] arr) {
int sum = 0; // 1번의 연산
// 배열의 길이(n)만큼 반복문이 실행된다.
for (int i = 0; i < arr.length; i++) {
sum += arr[i]; // n번의 연산
}
return sum;
}
- 로그 시간 (Logarithmic Time)
입력 데이터(n)의 크기가 커져도 실행 시간은 매우 조금씩 증가하는 알고리즘이다. 한 번의 연산마다 탐색해야 할 데이터의 양이 절반씩 줄어드는 경우가 대표적이며, 매우 효율적인 알고리즘이다.
// 이진 탐색(Binary Search)의 핵심 로직
int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
// left가 right를 넘어설 때까지 반복
// 반복할수록 탐색 범위가 절반씩 줄어든다.
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // 찾았을 경우
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 찾지 못했을 경우
}
- 제곱 시간 (Quadratic Time)
입력 데이터의 크기(n) 가 커질 때 실행 시간이 제곱에 비례하여 증가하는 알고리즘이다. 이중 for 문과 같이 for 반복문이 중첩되어 사용 되는 경우가 대표적이다.
// 이중 for문으로 모든 요소를 서로 비교한다.
boolean hasDuplicates_On2(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] == arr[j]) return true;
}
}
return false;
}
외부 루프가 n번, 각각에 대해 내부 루프가 또 n 번 실행되므로 총 연산 횟수는 n^2 이다.
백준 알고리즘에서 시간 초과는 대부분 이중 for 문 때문에 발생하는 경우가 많으며, 해당 부분만 개선해 줘도 시간 복잡도가 크게 개선된다.
개선 후 코드
O(1)의 탐색 성능을 가진 HashSet 자료구조를 활용하여 내부 for문을 제거한다.
import java.util.HashSet;
import java.util.Set;
// HashSet을 이용해 한 번의 순회만으로 중복을 찾는다.
boolean hasDuplicates_On(int[] arr) {
Set<Integer> uniqueSet = new HashSet<>();
for (int num : arr) {
// 이미 set에 들어있는 값이라면 중복이다. (O(1)만에 확인)
if (uniqueSet.contains(num)) {
return true;
}
// 아니라면 set에 추가한다.
uniqueSet.add(num);
}
return false;
}
시간 복잡도를 바탕으로 코드 로직 개선하기
1. 상수는 시간 복잡도 계산에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.
* 이중 for 문 (반복문) 의 경우 N *N 으로 제곱이기 때문에 시간이 오래 걸림. 일반 for 문 10개보다 이중 for 문 하나가 더 시간이 오래걸림. 때문에, 가장 많이 중첩되는 중첩문을 기준으로 봐야한다.
정리
1. 알맞은 알고리즘 쓰기 (선택기준)
2. 비효율적인 로직 찾아 효율적으로 변경
| 시간 복잡도 | 명칭 | 대표 예 |
| 상수 시간 | 배열 인덱스 접근 | |
| 로그 시간 | 이진 탐색 (Binary Search) | |
| 선형 시간 | for 문을 이용한 배열 순회 | |
| 선형 로그 시간 | 병합 정렬, 퀵 정렬 | |
| O(n^2) | 제곱 시간 | 이중 for문을 이용한 정렬 (버블, 선택) |
| O(2^n) |
지수 시간 | 재귀를 이용한 피보나치 수 |
시간 복잡도 알고리즘을 풀다보면 60프로는 이해할 수 있다 !! (나머지 40 프로는 수학공식 적용이라고 느껴진다.)
* 시간 복잡도 알고리즘 문제 모음으로 이동하기
https://www.youtube.com/watch?v=XncTU-4i1KI&t=29s
