복잡도(시간 복잡도, 공간 복잡도)
이번에 작성할 내용은 자료구조와 알고리즘을 하며 접한 복잡도에 대한 정리입니다. ✅
복잡도
복잡도란 알고리즘의 성능을 객관적으로 평가하는 기준입니다. (하드웨어나 컴파일러 등에 따라 달라지는 프로그램 실행속도와는 차이가 있습니다.)
복잡도의 종류
- 시간 복잡도 : 실행에 걸리는 시간을 평가하는 것
- 공간 복잡도 : 실행에 필요한 메모리가 얼마나 필요한가를 평가한 것
먼저 두 가지를 알아보기 전 복잡도를 표기하는 표기법 중 가장 널리 쓰이는 Big-O표기법을 알아보도록 하겠습니다.
Big-O 표기법
Big-O 표기법의 간단한 특징을 먼저 살펴보겠습니다.
- 컴퓨터에게 영향이 미미한 것은 무시한다.
- 상수항은 무시한다.
- 계수도 무시한다.
- 더 나아가 영향력이 없는 항을 무시한다.
- 추가적으로 설명하자면 컴퓨터에게 1번 실행한 것과 100번 실행한 것은 영향이 미미하여 O(1)로 표기한다고 생각하면 편하다.
- 예시) O(2n + 1) ▶️ O(2n) ▶️ O(n)
- 위의 예시에서 O(n)은 n(입력되는 데이터 수)에 비례하게 실행된다는 뜻입니다.
시간 복잡도 ⏰
int x = 1; // O(1)
int y = 2; // O(1)
System.out.println(x + y);
아주 간단한 위의 코드를 보면 변수 x, y를 초기화하고, 더한 값을 출력해 주었습니다.
그리고 주석으로 이 간단한 코드를 Big-O 표기법으로 시간 복잡도를 표현해 보았습니다.
설명을 추가하자면 O(1) 이란 1번의 실행만 일어난다는 뜻이다.(x, y를 각각 위의 값으로 초기화하면 1번의 실행만 필요하다.)
해당 코드의 시간 복잡도 계산은 O(1) + O(1) = O(max(1,1)) = O(1), 즉 O(1)이라고 표현합니다.
다음은 선형 검색 메소드를 통해 시간 복잡도를 계산해 보도록 하겠습니다.
public static int seqSearch(int[] a, int n, int key){
int i = 0; // O(1)
while (i < n){ // O(n)
if (a[i] == key){ // O(n)
return i; // O(1)
}
i++; // O(n)
}
return -1; // O(1)
}
위와 같은 방식으로 O(1) + O(n) + O(n) + O(1) + O(n) + O(1) = O(max(1, n, n, 1, n, 1)) = O(n)입니다.
여기서 while(i < n)은 실행 횟수가 n/2이고 O(n/2) ▶️ O(n) (Big-O표기법 특징) 표시됩니다.
위에서 살펴본 선형검색처럼 자료구조들의 시간복잡도를 Big-O표기법으로 표로 살펴보겠습니다.
| 복잡도 | 예시 |
| O(1) | stack pop, push |
| O(log n) | 이진 검색 |
| O(n) | 선형 검색 |
| O(n log n) | 퀵 정렬, 병합 정렬, 힙 정렬 |
| O(n^2) | 삽입 정렬, 선택 정렬, 버블 정렬 |
| O(2^n) | 피보나치 수열 |
공간 복잡도 💾
public static int seqSum(int n){
int sum = 0;
for (int i = 1; i <= n; i++){
sum += i;
}
return sum;
}
위의 코드를 살펴보면 주어진 n 값에 상관없이 sum이라는 변수 하나만을 사용하여 합을 계산하고 있으므로, 공간 복잡도는 O(1)입니다. 앞서 정의에서 살펴본 것과 같이 시간 복잡도와는 복잡도를 평가하는 기준이 달라졌습니다.
public static int factorial(int n){
if(n == 1){
return 1;
}
return n * factorial(n - 1);
}
위의 코드는 수학의 n!(팩토리얼) 메소드입니다. 이 코드에서 n은 재귀호출로 n번 발생할 수 있으므로, 공간 복잡도는 O(n)입니다.
공간 복잡도는 시간 복잡도를 이해하셨다면 시각을 조금 달리해 이해할 수 있다고 생각되었습니다!
코딩테스트를 위한 복잡도 ⏳
코딩테스트 연습을 위해 연습 사이트를 접속하여 문제를 보면 위와 같은 이미지가 있습니다.
실제 코딩테스트를 본다면 주어진 시간과 입력 크기에 대해 정확한 결과를 도출해야 하기 때문에 복잡도 내에서 해결할 수 있는 알고리즘을 구현해야 합니다.(보통 시간은 1초 이내, 메모리는 조금씩 다름.)
연습을 할 때 무작정 문제를 푸는 것보다는 복잡도를 고려하여 최적의 풀이 방법을 모색하는 것도 연습이 필요하다고 생각합니다. 물론 저도 지금은 잘되지 않는 부분이지만 앞으로 유념하며 문제를 풀어나가고 문제풀이도 포스팅해보도록 하겠습니다!
| 입력 크기 | 시간 복잡도 |
| 20 | O(n!), O(2^n |
| 500 | O(n^3) |
| 10^4 | O(n^2) |
| 10^6 | O(n log n) |
| 10^8 | O(n), O(log n) |