[알고리즘]알고리즘 수행시간을 비교해 볼까?

알고리즘이란?

- 입력 : 외부에서 제공되는 자료가 0개 이상 제공된다.

- 출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.( 즉 모든 입력에서 하나의 출력이 나오면 안됨)

- 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성

- 유한성 : 유한번의 명령을 수행 후 종료된다.

- 효율성 : 모든 과정은 명백하게 실행가능(검증가능) 한것이어야 한다.

 

 

좋은 알고리즘이란?

- 정확성 : 적당한 입력에 대해서 유한 시간내에 답을 산출하는가? 를 판단.

- 작업량 : 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정

- 기억장소 사용량 : 수행 과정에서 필요한 저장공간

- 최적성 : 그 알고리즘보다 더 적은 연산을 수행하는 알고리즘은 없는가?

(단, 최적이란 가장  '잘 알려진' 이 아닌 '가장 좋은' 의 의미이다.)

- 시간 복잡도 : 최적의 시간으로 연산을 수행하는 알고리즘인가?

(단, 빠른 시간안에 해결이 된다고 해도 정확성이 떨어진다면? 혹은 정확성은 약간의 오차가 발생하는데 시간 차이가 많이 발생한다면?)

 

 

 

시간 복잡도

- 문제를 해결하는데 걸리는 시간과 입력의 함수 관계

- 가장 많이 사용하는 빅오표기법(O) : 알고리즘의 효율성을 상한선 기준으로 표기한다.(1부터 5000까지의 수가 있는 경우 어떤 수의 위치를 찾을때 최대 5000 번을 수행한다고 하면 빅오표기법에서 수행시간은 5000 이라고 생각하는 것이다.)

 

 

빅오표기법

- O(1) : 입력 자료에 관계 없이 동일한 실행 시간을 갖는 알고리즘 

예)

int main()
{
	int a[] = {1,2,3,4,5,6,7,8,9,10};
           int b;
           scanf(“%d”,&b);
           printf(“%d”,a[b]);
}

 

 

- O(logN) : 입력자료가 N일경우 log2N의 시간

예)

int f(int n)
{
	int a[] = {1,2,3,4,5,6,7,8,9,10};
           int b;
           int s =0;
           int e = 9;
           while(1){
		if(s>=e) return -1; //찾지 못했다.
		int m = (s+e) /2;
 		if(a[m]==n) return  m;
		if(a[m]>n) s=m+1;
                      else e = m-1;
	} 

}

 

 

- O(N) : 입력 자료가 N일경우 N시간

예)

int f(int n)
{
	int a[] = {1,2,3,4,5,6,7,8,9,10};
           int b;
           for(int i=0;i<10;i++) if(a[i]==n) return I;
	return -1;
}

 

 

- O(NlogN) : 입력자료가 N일경우 Nlog2N의 시간

예)

int quick_Sort(int start, int end)
{
    int tempValue;
    if(start < end)
    {
        int left = start-1, right = end+1, pivot = a[start];
        while(left<right)
        {
            while(a[++left]<= pivot);
            while(a[--right] > pivot);
            if(left >= right) break;
	swap(a[left],a[right]);
        }
        swap(a[start],a[right]);
        quick_Sort(start, right-1);
        quick_Sort(right + 1, end);
    }
}

 

 

- O(N²) : 입력 자료가 N일경우 N * N 시간

예)

int f(int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) printf( “%d “,i*j);
		printf(“\n”);
	}
}

 

 

- O(N³) : 입력 자료가 N일경우 N * N * N 시간

예)

int f(int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) 
		{
			for(int k=1;k<=n;k++) printf( “%d “,i+j+k);
			printf(“\n”);
		}
	}
}

 

 

- O(2ⁿ) : 입력 자료가 2^n 의 시간

예)

int dfs(int y,int x,int state)
{
	if(y>=n) return 1;
	if(x>=n) y++,x=0;
	int res = dfs(y,x+1,0) + 1;
    	res +=dfs(y,x+1,1) +1;
	return res;
}

 

 

 

수행시간 계산방법

- #include <time.h> 또는 #include <ctime> 선언
- clock() 함수를 이용해 프로그램 수행시간 측정

 

예)

int startTime,endTime;
startTime = clock();
//프로세스 수행
endTime= clock();
printf(“%.3lf”,(double)(endTime-startTime)/CLOCKS_PER_SEC);
 
//여기서 CLOCKS_PER_SEC 는 1000의 값으로 define 되어 있다.

 

 

오늘도 최선을 다하는 우리 학생들을 응원합니다.

인천 서구 검단신도시 원당컴퓨터학원