복잡도
- 시간 복잡도(Time Complexity)
: 얼마나 빠른가(CPU에게 얼마나 부담이 가는가?)
- 공간 복잡도(Space Complexity)
: 얼마나 메모리를 많이 사용하는가?
- 일반적으로 알고리즘을 평가할 때는 메모리의 사용량 보다 실행속도(시간 복잡도)에 초점을 둔다. 공간복잡도는 알고리즘을 평가하는데 있어서 보조적인 열할을 한다. 메모리를 얼마나 쓰느냐는 것은 메모리에 데이터를 썼다 지웠다 하는 작업을 얼만큼 하느냐이다. 일반적으로 시간복잡도에 비래 메모리 access 시간이 극히 적게 걸리기 때문에 그리 중요하지 않다는 것이다.
순차 탐색(Linear Search) 알고리즘과 시간 복잡도 분석의 핵심요소
int LSearch(int arr[], int len, int target)
{
int i;
for (i=0; i<len; i++)
{
if (arr[i] == target)
return i;
}
return -1;
}
* 위 함수에서 수행되는 연산은 '<', '++', '==' 이다. 그럼 위에 for문이 한번 돌아갈때 마다 3번의 연산횟수를 모두 세야 하는가? 결론적으로 말하면 그렇지 않다. 저 세개의 연산중 핵심연산을 찾아 그 연산의 횟수만 세면 된다. 그렇다면 핵심연산을 찾는 기준을 알아야 할것이다. 핵심 연산이라는 것은 주변 연산의 실행 여부를 결정짓는 결정권자 라는 것이다. 위 코드로 예를 들면, '<', '++' 연산은 '==' 연산의 결과에 따라 실행 될수도 있고 되지 않을 수도있다. 그렇기 때문에 '==' 연산이 핵심 연산이라는 얘기이고, 복잡도를 계산할때 '=='연산의 횟수만 고려하면 된다.
최선의 경우? 평균적인 경우? 최악의 경우?
알고리즘의 성능을 판단할 때, 어떠한 경우를 기준으로 성능을 측정해야 할 지 궁금해 하는 사람들이 있을거이다. 먼저 최선의 경우는 고려할 필요가 없다. 대부분 알고리즘의 최선의 경우는 복잡도가 O(1)일 것이기 때문이다. 그렇다면 논리적으로 평균적인 경우를 기준으로 잡고 알고리즘을 측정해야 정확한 성능 측정이라고 말할 수 있는것 아닌가? 논리적으로 말하면 그렇지만 일반적으로 알고리즘의 평균적인 경우에 대한 복잡도를 측정하는것이 매우 힘들고, 어떠한 상황이 평균적인 경우라고 정의하는것 조차 애매하기 때문이다. 그래서 보통 알고리즘을 측정할 때는 최악의 경우(Worst Case)를 기준으로 측정한다.
* 위 순차탐색 알고리즘의 경우 데이터 갯수(배열안에 존재하는 데이터의 갯수)가 n개일때 최악의 경우 핵심연산을 n번 수행해야 하기 때문에 O(n)의 복잡도를 갖는다고 할 수 있다.
이진 탐색(Binary Search) 알고리즘의 소개
int BSearch(int arr[], int len, int target)
{
int first = 0;
int last = len - 1;
int mid;
while (first <= last)
{
mid = (first + last) / 2;
if (target == arr[mid])
{
return mid;
}
else
{
if (target < arr[mid])
last = mid - 1;
else
first = mid + 1;
}
}
return -1;
}
위 이진탐색 알고리즘의 복잡도는 O(log n)이다. 위 알고리즘의 핵심연산이 한번씩 수행될 때 마다 내가 고려해야 되는 데이터 갯수는 1/2로 줄어든다. 그러므로 데이터의 갯수 n이 1이 되기까지 2로나눈 횟수가 알고리즘의 복잡도이다. 이것을 수식으로 나타내면 log n이 되는것이다.(밑이 2인 log)
빅-오 표기법(Big-Oh Notation)
만약 어떤 알고리즘의 시간복잡도가 정확히 "T(n) = n^2 + n + 1" 이라면 빅오 표기법으로 표현할 때, O(n^2)으로 표현한다. 즉 빅오 표기법은 주어진 알고리즘 다항식에서 최고차항의 차수만 뽑아 표현하는 것이다.
T(n) = n^2 + 2n + 1 --> O(n^2)
T(n) = n^4 + n^3 + n^2 + 1 --> O(n^4)
T(n) = 5n^3 + 3n^2 + 2n + 1 --> O(n^3)
여기서 드는 의문, 아니 n^2 + 2n + 1의 경우 2n + 1을 맘대로 없애버려도 알고리즘을 정확히 측정했다고 할 수 있는가?
이 질문에 대답하기 전에 우리가 왜 알고리즘을 측정하는가에 대해서 고찰해 볼 필요가 있다. 처리해야 하는 데이터 갯수가 많지 않을때 알고리즘의 성능을 측정하는것이 의미가 있는가? 난 아니라고 본다. 데이터가 많지 않을경우는 왠만큼 알고리즘의 성능이 나빠도 큰 문제없이 프로그램을 돌아가기 마련이다. 우리가 알고리즘 성능 측정을 하는 이유는 데이터의 갯수가 아주 많을 때, 즉 기하 급수적으로 늘어날 때 프로그램의 성능을 떨어뜨릴만한 성능적으로 안좋은 영향을 미칠 수 있는가 또는 프로그램의 성능을 향상시킬 수 있는가에 대해서 알아보려고 하는것이다.
자 그러면, 위에 언급한 정의대로라면 알고리즘 성능 측정은 데이터 갯수가 많을때 의의가 있다. 아래 표를 보자.
T(n) = n^2 + 2n + 1 이라 가정.
n |
n^2 |
2n |
T(n) |
n^2의 비율 |
10 |
100 |
20 |
120 |
83.33% |
100 |
10,000 |
200 |
10,200 |
98.04% |
1,000 |
1,000,000 |
2,000 |
1,002,000 |
99.80% |
10,000 |
100,000,000 |
20,000 |
100,020,000 |
99.98% |
요즘 알고리즘에서 데이터 갯수가 1000개 10000개라고 해도 그렇게 많은 데이터 갯수가 아니다. 그럼에도 불구하고 빅오 표현법에서 살아 남는 n^2의 비율이 T(n)의 99프로 이상을 차지한다. 그렇기 때문에 과감하게 최고차항의 차수를 제외하고 성능을 고려해도 아무 문제가 없다는 것이다.
O(1)
- 상수형 빅-오, 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘이다.
0(logn)
- 로그형 빅-오, 로그의 밑이 얼마냐에 따라서 차이가 나긴 하지만 그 차이는 알고리즘의 성능관점에서 매우 미미하기 때문에 대부분의 경우에 있어서 무시가 된다. 일반적으로 매우 만족스러운 속도의 알고리즘이다.
0(n)
- 선형 빅-오, 데이터의 수와 연산횟수가 비례하는 알고리즘이다.
0(nlogn)
- 선형 로그형 빅-오, 알고리즘 중에 이에 해당하는 알고리즘이 적지 않다.
0(n^2)
- 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘, 중첩 반복문이 보통 이 형태를 띈다. 따라서 알고리즘 디자인에서 그리 바람직하지 못한 형태이다.
0(2^n)
- 지수형 빅-오, 가장 성능이 좋지않은 알고리즘이다.
*성능: O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(2^n)
*순차 탐색 VS 이진 탐색 알고리즘 성능 비교
n |
순차 탐색 연산횟수 |
이진 탐색 연산횟수 |
500 |
500 |
9 |
5,000 |
5,000 |
13 |
50,000 |
50,000 |
16 |
LinkedRead.c
