어떤 문제가 주어졌을때, 그에 맞추어 알고리즘을 적용하거나 새로 만들어서
해답을 구할수 있다고 하자. 하지만 적은 데이터량에서는 분명히 빠르게, 그리고 잘 돌아가던
알고리즘이 어느순간 몇백년이 걸리는 프로그램이 될 수 있다는 것을 생각해보았는가?
이번에는 함수의 복잡도 라는 개념을 이해해보도록 하고,
그 어마어마한 수와 시간의 변화에 한번 놀라보도록 하자.
참고 : 자료의 수와 용도를 고려하여
버블정렬, 퀵정렬, 등의 정렬 알고리즘의
중요성을 다시한번 생각해보자.
문제) 시험점수의 점수별 순위를 구하여라.
data : 56 25 67 88 100 61 55 67 76 56
첫번째 알고리즘
1. 데이터의 갯수에 따라 각 순위를 저장할 rank 배열을 갯수만큼 할당한다.
2. 각 rank[i]의 값은 1로 초기화된다.
필요한변수 int rank[Nuim]; (Num = 총 데이터의 갯수)
3. i번째 데이터의 값을 나머지 값들과 순서대로 비교해 나가면서 i번째 데이터보다
큰 값이 있을때에는 rank[i] 에 1을 더한다.
4. 자료의 끝까지 3번을 반복한다.
5. 자료의 수 만큼 2-4번을 반복한다.
#include <stdio.h>
#define Num 10
void main(void){
static int a[] = {56, 25, 67, 88, 100, 61, 55, 67, 76, 56};
int rank[Num];
int i, j;
for(i=0 ; i<Num ; i++){
rank[i] = 0;
for(j=0 ; j<Num ; j++){
if(a[j] > a[i]){
rank[i]++;
}
}
}
printf(" 점수 | 순위 \n" );
for(i=0 ; i<Num ; i++){
printf("%6d|%6d\n", a[i], rank[i]);
}
}
이 알고리즘은 자료의 갯수가 n개 일때, 총 n x n 번의 실행횟수가 예상된다.
이를 알고리즘의 복잡도 라고 하며, O(n^2)로 표현한다.
예를들어, y = ax^3 + b 인 식이 있을경우,
이 식은 x의 값이 커짐에 따라서 a와 b는 무시할수 있는 값이 되므로,
복잡도는 O(n^3)으로 표현하게 된다.
두번째 알고리즘(실행속도 개선)
점수의 범위를 0~100 이라고 할때, 이를 배열의 첨자로 삼는다.
즉, rank[100]의 배열에 추가로 여분을 두어 rank[101]을 할당한다.
1. 먼저 각 자료의 값에 해당하는 rank[i]에 1씩을 더한다.
2. rank[101]에 초기값 1을 넣는다.
3. rank[100]에서 부터 rank[0]에 이르기까지, 각 항에
바로 오른쪽(상위)요소의 값을 더해나간다.
: 89점인 자료의 순위값은 rank[90]에 저장된다.
0 1 2 3 ...... ..... 87 88 89...............98 99 100 101 배열의 첨자번호
11 11 11 11 3 3 2 2 2 2 1 rank[i]의 값
#include <stdio.h>
#define Num 10
#define Max 100
#define Min 0
void main(void){
static int a[] = {56, 25, 67, 88, 100, 61, 55, 67, 76, 56};
int i, rank[Max+2] // 추가적인 공간을 더 잡아준다.
for(i=Min ; i<=Max ; i++){
rank[i] = 0; // 초기화 작업
}
for(i=0 ; i<Num ; i++){
rank[a[i]]++; // 먼저 각 값에 해당하는 배열의 자리에 1씩을 더한다.
} // 중복값이 있더라도 모두 실행한다.
rank[Max+1]=1;
for(i=Max ; i>=Min ; i--){
rank[i] = rank[i] + rank[i+1];
}
printf(" 점수 | 순위\n");
for(i=0; i<Num ; i++){
printf("%6d|%6d\n", a[i], rank[a[i]+1]);
}
}
이 알고리즘은 n개의 값이 있고, 그 범위가 m일 때에
n x m 번의 반복만으로 순위를 매길수 있고, 복잡도는 O(n)으로 표현한다.
함수의 복잡도는 O(log2n) < O(n) < O(log2n-n) < O(n^2) < O(n^3) < O(2^n) < O(n!)
와 같이 그 순서를 정한다.
알고리즘의 복잡도 표현에서 n을 기준으로하는 for구문이 여러개나 되는데
왜 O(n)으로 표시하는가에 의문을 가질 수 있겠지만,
이는 n의 값이 점점 커짐에 따라서 상수가 가지는 비중이 점점 보잘것 없어지기 때문이다
y = 6x + 3 ------(1)
y = x^2 ------(2) 이와같은 두개의 함수에서
x =1일때, (1) = 9 , (2) = 1 n이 작을 경우에는 O(n^2)의 실행횟수가 더 작을수 있다.
x =2일때, (1) = 15 , (2) = 4
x =3일때, (1) = 21 , (2) = 9
. .
. .
. .
x =10일때, (1) = 63 , (2) = 100 n이 커져갈 수록 O(n^2)의 실행횟수는 빠르게 늘어간다.
x =11일때, (1) = 69 , (2) = 121
x =20일때, (1) = 123 , (2) = 400
때문에 복잡도를 매김할때에는 상수를 가늠하지 않는다.
실제로 O(x^3)의 복잡도를 가진 경우에,
n의 값이 10000이 되면, 1,000,000,000,000번의 반복실행이 필요하며,
초당 1억번의 반복을 수행할수 있다고 할때, 1000 초의 수행시간이 필요하게 되며,
n의 값이 20000이 되면, 8000(약 2시간)초
n의 값이 50000이 되면, 125,000초(약 34시간) 가 필요하게 된다.
최악의 경우인 O(n!)에서는 n의 값이 20만 되어도, 2432902008초(약 77년)가 걸리게 된다.
