시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)
알고리즘을 평가할 때 시간 복잡도와 공간 복잡도를 사용합니다.
- 시간 복잡도: 알고리즘의 수행시간을 평가
- 공간 복잡도: 알고리즘 수행에 필요한 메모리 양을 평가
시간 복잡도와 공간 복잡도는 주로 점근적 표기법 중 빅오 표기법을 이용하여 나타냅니다.
이유는 최악의 경우에도 해당 알고리즘이 어떤 성능을 낼지 가늠해볼 수 있기 때문입니다.
시간 복잡도(Time Complexity)
알고리즘의 수행 시간을 분석할 때 시간 복잡도를 사용합니다.
수행 시간은 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가합니다.
기본 연산은 다음과 같습니다.
- 데이터 입출력 - copy, move...
- 산술 연산 - add, multiply ...
- 제어 연산 - if, while ...
시간 복잡도는 3가지 경우로 나타냅니다.
- 최선의 경우 (Best Case)
- 빅 오메가 표기법 사용
- 최선의 시나리오로 최소 이만한 시간이 걸림
- 최악의 경우 (Worst Case)
- 빅 오 표기법 사용
- 최악의 시나리오로 아무리 오래 걸려도 이 시간보다 덜 걸림
- 평균적인 경우 (Average Case)
- 빅 세타 표기법 사용
- 평균 시간을 나타냄
평균적인 경우를 가장 많이 사용할 것 같지만 알고리즘이 복잡해질수록 평균적인 경우는 구하기가 매우 어려워 지기 때문에 최악의 경우로 알고리즘의 성능을 파악합니다.
시간 복잡도 계산
시간 복잡도는 일반적으로 빅오 표기법으로 나타냅니다.
연산 횟수가 다항식으로 표현될 경우, 최고차항을 제외한 모든 항과 최고차항의 계수를 제외시켜 나타냅니다.
예를 들어 입력 크기가 n이라고 했을 때 다음과 같이 표기합니다.
- \(T(n) = n^2+2n+1 = O(n^2)\) : 최고차항만 나타냄.
- \(T(n) = 2n = O(n)\) : 최고차항의 계수는 제외함.
다음 알고리즘을 가지고 시간 복잡도를 구해보겠습니다.
int func (int n) {
int sum = 0; // 대입연산 1회
int i = 0; // 대입연산 1회
for(i=0; i < n; i++) { // 반복문 n+1회
sum += i; // 덧셈 연산 n회
}
for(i=0; i < n; i++) { // 반복문 n+1회
sum += i; // 덧셈 연산 n회
}
return sum; // 리턴 1회
}위 알고리즘에 단계별 연산 횟수는 주석과 같고 총 연산 횟수는 4n+5입니다.
그러므로 이 알고리즘의 시간 복잡도는 다음과 같습니다.
$$ T(n) = 4n+5 = O(n) $$
시간 복잡도 표기
\(O(1)\) - 상수 시간 (Constant time)
입력 크기(n)에 상관없이 일정한 연산을 수행하면 시간복잡도는 O(1)입니다.
void func (int n) {
printf("%d\n", n);
}위 알고리즘은 n에 상관없이 한 번에 연산만 수행하기 때문에 시간 복잡도는 다음과 같습니다.
$$T(n)=O(1)$$
\(O(logN)\) - 로그 시간 (Logarithmic time)
입력 크기(N)가 커질 때 연산 횟수가 logN에 비례해서 증가하면 시간 복잡도는 O(logN)입니다.
for(i=1; i<=n; i*2) {
...
}위 알고리즘은 i 값이 반복할 때마다 2배씩 증가합니다. 이것을 k번 반복했을 때 다음과 같습니다.
\(2^k =N\) 이 되고 반복문이 종료됩니다. 양쪽에 로그를 취하면 다음과 같습니다.
$$log_2(2^k) = log_2N$$
$$k = log_2N$$
k는 수행 횟수이기 때문에 시간 복잡도는 다음과 같습니다.
$$T(n) = logN$$
\(O(n)\) - 선형 시간 (Linear time)
입력 크기(n)가 커질 때 연산 횟수가 n에 비례해서 증가하면 시간 복잡도는 O(n)입니다.
- 연산횟수가 선형적으로 증가하는 형태
for(i=0; i < n; i++) {
...
}위 알고리즘은 n만큼 반복문을 수행합니다.
n에 값에 비례해서 연산수가 선형적으로 증가하기 때문에 시간 복잡도는 다음과 같습니다.
$$T(n) = O(n)$$
\(O(n^2)\) - 2차 시간 (Quadratic time)
입력 크기(n)가 커질 때 연산 횟수가 \(n^2\)에 비례해서 증가하면 시간 복잡도는 \(O(n^2)\)입니다.
for(i=0; i < n; i++) {
for(j=0, j < n; j++) {
...
}
}위 알고리즘은 for문이 중첩되어 있기 때문에 \(n^2\)에 비례해서 연산수가 증가합니다.
시간 복잡도는 다음과 같습니다.
$$T(n) = O(n^2)$$
\(O(2^n)\) - 지수 시간 (Exponential time)
입력 크기가 커질 때 연산수가 \(2^n\)에 비례해서 증가하면 시간 복잡도는 \(O(2^n)\)입니다.
int func (int n) {
if (n <= 1)
return n;
return func(n-1) + fun(n-2);
}위 알고리즘은 피보나치 수를 구하는 알고리즘입니다.
한번 함수를 호출할 때마다 두 번씩 재귀로 함수를 호출하기 때문에 \(2^n\)에 비례해서 연산수가 증가합니다.
시간 복잡도는 다음과 같습니다.
$$T(n) = O(2^n)$$
다음은 빅오 표기법으로 표현한 알고리즘의 성능 간 그래프입니다.
$$O(1) < O(log n) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!)$$
오른쪽으로 갈수록 시간 복잡도가 큰(수행 시간이 긴) 알고리즘입니다.
n의 값이 작을 때는 알고리즘 사이에 큰 차이가 없지만 n의 값이 커지면 커질수록 복잡한 알고리즘은 수행 시간이 급격히 길어지게 됩니다.
시간 복잡도를 낮출 수 있다면 프로그램에 큰 성능 향상을 기대할 수 있습니다.
공간 복잡도(Space Complexity)
공간 복잡도는 알고리즘에서 사용하는 메모리 양을 나타냅니다.
공간 복잡도는 보조공간(Auxiliary Space)과 입력 공간(input size)을 합친 포괄적인 개념입니다.
보조 공간(Auxiliary Space)은 알고리즘이 실행되는 동안 사용하는 임시 공간입니다.
그렇기 때문에 입력 공간(input size)을 고려하지 않습니다.
공간 복잡도 계산
공간 복잡도도 시간 복잡도와 유사하게 빅오 표기법을 사용합니다.
다음 알고리즘을 보고 공간 복잡도를 계산해 보겠습니다.
int sum(int a[], int n)
{
int x = 0;
for(int i = 0; i < n; i++) {
x = x + a[i];
}
return(x);
}위 알고리즘은 4개의 변수를 사용하고 있습니다.
- int arr[n] : 4*n byte (입력 공간)
- int n : 4 byte (입력 공간)
- int x : 4 byte (보조 공간)
- int i : 4 byte (보조 공간)
총 4n+12 에 메모리를 요구합니다. 메모리가 입력 값에 따라 선형적으로 증가하기 때문에 공간 복잡도는 O(n)이 됩니다.
