알고리즘 문제를 풀고나서 설명을 할때 꽤 자주 면접에 들어온 엔지니어들이 해당 코드의 시간 복잡도나 공간 복잡도에 대해서 물어볼때가 있다. 그래서 시간 복잡도는 무엇인지 그리고 공간 복잡도는 무엇이고 계산을 어떻게 하는지 적어보려고 한다.
1. 시간 복잡도란?
코드를 작성했다고 치자. 해당 코드의 실행시간을 수학적으로 풀어쓴 것이라고 보면 된다. 좀더 정확히 말해서, 코드의 실행 시간이 얼마나 걸릴것인지를 시간 복잡도라고 한다. 입력 크기 n에 따라 알고리즘이 실행되는 데 필요한 연산 횟수이다.
보통은 최악의 경우를 기준으로 분석하고 빅오 표기법을 사용한다.
2. 시간 복잡도 계산법
- 코드에서 반복문과 연산 횟수를 기준으로 연산량을 세어보면된다.
int getFisrtElement(int arr[], int n) {
return arr[0]; // 항상 0번째 요소를 반환
}만약 위처럼 단순히 배열이 들어오면 0번째 요소를 반환하는 함수가 있다고 가정한다면. 해당 함수의 실행시간은 배열의 길이에 상관없이 항상 한번만 연산을 하면 된다. 따라서 위 함수의 시간 복잡도는 O(1)이다. 이는 "상수 시간"으로 읽기도 한다.
코드 상에서는 반복문을 실행할 일이 많다. for문, while문들이 있는데 이 경우에도 총 연산횟수로 계산하면된다.
int sumArray(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++) { // n번 반복
sum += arr[i];
}
return sum;
}반복문이 n번 실행되기 때문에 O(n)으로 볼 수 있다. 이럴 경우 이 sumArray함수의 시간 복잡도는 n에 선형적으로 비례한다고 말할 수 있다. 그리고 만약 for문 안에 for문이 하나 더 있다면 n의 제곱이 된다.
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}Binary Search(이진 탐색)를 할 경우에는 범위가 매번 절반으로 줄어든다. 따라서 이 경우 시간은 log n으로 표기한다.
3. 공간 복잡도란?
입력 크기 n에 따라 알고리즘이 사용하는 메모리 공간의 양을 나타낸다. 보통 사용하는 변수, 배열, 재귀 호출 스택 등을 기준으로 계산한다.
4. 공간 복잡도 계산법
고정 공간, 가변 공간으로 나눠서 계산할 수 있는데 고정 공간이란 입력 크기와 무관하게 항상 사용되는 공간이고 가변 공간은 입력 크기에 따라 변하는 공간을 말한다.
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1); // 재귀 호출
}
재귀 호출이 n에서 0까지 호출 스택에 쌓이기 때문에 O(n) 공간을 사용한다.
