[C언어로 쉽게 풀어쓴 자료구조] 1.3 알고리즘의 성능 분석

자료구조 복습

 

교재 : c언어로 쉽게 풀어쓴 자료구조 (개정 3판) - 청인국, 공용해, 하상호 지음

 

 

 

1.3 알고리즘의 성능 분석

 

 

요즘 컴퓨터는 예전의 컴퓨터에 비하여 엄청난 계산속도와 방대한 메모리를 자랑하고 있으며 계쏙하여 발전을 거듭하고 있음. 

하지만 요즘에도 여전히 프로그램의 효율성은 중요함.

 

이유 : 

• 최근 상용 프로그램의 규모가 이전에 비하여 엄청나게 커지고 있음. 처리해야할 자료의 양이 많기 때문에 알고리즘의 효율성이 더욱 중요함.
• 사용자들은 여전히 빠른 프로그램을 선호함.

 

효율적인 알고리즘 : 

알고리즘이 시작하여 결과가 나올 때까지의 수행시간이 짧으면서 컴퓨터 내에 있는 메모리와 같은 자원을 덜 사용하는 알고리즘.

 

 

수행시간 측정방법

가장 단순하지만 가장 확실한 방법.

알고리즘을 프로그래밍 언어로 작성하여 실제 컴퓨터상에서 실행시킨 다음, 그 수행시간을 측정하는 것.

 

예 :

알고리즘1, 알고리즘2 (둘 다 돌일한 조건에서 동일한 작업을 함)

알고리즘1 : 10초

알고리즘2:  50초

효율적인 알고리즘 : 알고리즘1 > 알고리즘2

 

 

C언어에서 수행시간을 측정하는 방법 2가지 : 

 

방법1 ; 

#include <time.h>

start = clock();
...
stop = clock();
double duration = (double)(stop - start) / CLOCKS_PER_SEC;

clock() 함수 : 호출 프로세스에 의하여 사용된 CPU 시간을 계산.

clock() 함수는 호출되었을 때의 시스템 시각을 CLOCKS_PER_SEC 단위로 반환.

수행시간을 알기위해서는 먼저 알고리즘을 시작하기 전에 한 번 clock() 함수를 호출하여 start 변수에 기록하고, 알고리즘이 끝나면 다시 clock() 함수를 호출하여 stop 변수에 기록한 다음, 초단위의 시간을 측정하기 위하여 (stop - start) 값을 CLOCKS_PER_SEC으로 나누어 주면 됨.

 

 

방법2 : 

#include <time.h>

start = time(NULL);
...
stop = time(NULL);
double duration = (double) difftime(stop, start);

time() 함수는 초 단위로 측정된 시간을 반환. time(NULL) 형태로 호출하면 현재 시간이 넘어옴. 

프로그램의 시작과 종료 시점에서 time(NULL)을 호출한 후, 두 가지 시간을 difftime()으로 보내면 차이가 초단위로 반환.

 

 

방법1 사용한 코드 예 : 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void)
{
	clock_t start, stop;
	double duration;
	start = clock();	// 측정 시작

	for (int i = 0; i < 1000000; i++)	// 의미 없는 루프
		;
	stop = clock();		// 측정 종료
	duration = (double)(stop - start) / CLOCKS_PER_SEC;
	printf("수행시간은 %f초입니다.\n", duration);
	return 0;
}

 

문제점 : 

알고리즘을 구현하고 테스트하는 것이 필요.

알고리즘이 비교적 단순한 경우에는 쉽게 구현할 수 있지만 복잡한 경우에는 구현해야 된다는 점이 큰 부담이 될 수 있음.

반드시 똑같은 하드웨어를 사용하여 알고리즘들의 수행시간을 측정하여야 함. 

슈펴컴퓨터상에서는 아주 비효율적인 프로그램이라 하더라도 퍼스널 컴퓨터상에서의 가장 효율적인 프로그램보다 더 빠른 시간에 수행될 수 있기 때문.

사용한 소프트웨어 환경도 중요함.

프로그래밍에 사용한 컴퓨터 언어에 따라 수행 속도가 달라질 수 있음.

일반적인 경우, C와 같은 컴파일 언어를 사용한 경우가 베이직과 같은 인터프리트 언어를 사용한 경우보다 빠른 수행을 보임.

실험에 사용했던 데이터가 아닌 다른 데이터에 대해서는 전혀 다른 결과가 나올 수 있음.

실험되지 않은 입력에 대해서는 수행시간을 주장할 수 없음.

 

 

알고리즘의 복잡도 분석방법

구현하지 않고서도 알고리즘의 효율성을 따져보는 기법이 개빌됨.

 

알고리즘 복잡도 분석 (complexity analysis) : 

구현하지 않고도 모든 입력을 고려하는 벙법. 실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있음.

 

 

시간 복잡도 함수

알고리즘 분석의 2가지 측면 : 

1. 알고리즘의 수행시간
2. 알고리즘이 필요로 하는 기억공간의 양

 

• 시간 복잡도 (time complexity) : 알고리즘의 수행시간 분석
• 공간 복잡도 (space complexity) : 알고리즘이 사용하는 기억공간 분석

 

우리가 알고리즘의 복잡도를 이야기할 때 대개는 시간 복잡도를 의미.

알고리즘이 차지하는 공간보다는 수행시간에 더 관심이 있기 때문.

 

 

시간 복잡도 : 

알고리즘의 절대적인 수행 시간을 나타내는 것이 아님.

알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표시.

알고리즘의 복잡도를 분석할 때 연산의 수행횟수를 사용.

 

연산들의 수행횟수는 보통 그 값이 변하지 않는 상수가 아님.

연산들의 수행횟수는 보통 프로그램에 주어지는 입력의 개수 n에 따라 변하게 됨.

따라서 일반적으로 연산의 수행횟수는 고정된 숫자가 아니라 n에 대한 함수가 됨.

연산의 수를 입력의 개수 n의 함수로 나타낸 것을 시간복잡도 함수라고 하고 T(n)이라고 표기.

 

 

예 : 

알고리즘1	알고리즘2	알고리즘3
sum←n*n;	for i←1 to n do     sum ←sum+n;	for i←1 to n do      for j←1 to n do           sum←sum+ 1;

 

	알고리즘A	알고리즘B	알고리즘C
대입연산	1	n	n * n
덧셈연산		n	n * n
곱셈연산	1
나눗셈연산
전체연산수	2	2n	2n^2

하나의 연산이 t만큼의 시간이 걸린다고 하면 알고리즘A는 2t에 비례하는 시간이 필요하고 알고리즘B는 2nt의 시간이, 알고리즘C는 2n^2t만큼의 시간이 걸림. 

n이 커질수록 알고리즘간의 차이는 커지게 됨.

따라서 연산의 개수를 이용하여 알고리즘들을 비교하고 비교한 결과를 바탕으로 가장 효율적인 알고리즘을 선택할 수 있음.

 

 

빅오 표기법

시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도 를 표시하는 방법.

 

알고리즘이 n에 비례하는 수행시간을 가진다고 말하는 대신 알고리즘 A의 시간복잡도가 O(n)이라고 함.

O(n)은 '빅오 of n'이라고 읽음.

빅오 표기법은 n의 값에 따른 상한값을 나타내는 방법

 

빅오 표기법 정의 : 

두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n>n0에 대하여 |f(n)|<=|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n) = O(g(n))이다.

 

빅오 표기법을 얻는 간단한 방법 ; 

기본연산의 횟수가 다항식으로 표현되었을 경우 다항식의 최고차항만을 남기고 다른 항들과 상수항을 버리는 것.

최고차항의 계수도 버리고 단지 최고차항의 차수만을 사용

 

예 : 

5n^4 + 4n^3 + ... + 2n + 1 = O(n^4)

 

많이 쓰이는 빅오 표기법 순서 : 

1. O(1) : 상수형
2. O(log n) : 로그형
3. O(n) : 선형
4. O(n log n) : 선형로그형
5. O(n^2) : 2차형
6. O(n^3) : 3차형
7. O(2^n) : 지수형
8. O(n!) : 팩토리얼형

빅오 표기법은 입력의 개수에 따른 기본 연산의 수행 횟수를 개략적으로 나타낸 것.

이것을 이용하여 알고리즘의 대략적인 수행시간을 추정가능

 

빅오 표기법에 의한 알고리즘의 수행시간 : 

O(1) < O(log n) < O(n) < O(n log n) < (n^2) < O(2^n) < O(n!)

 

 

빅오표기법 이외의 표기법

빅오메가 표기법 : 

어떤 함수의 하한을 표시하는 방법

 

빅오메가 표기법 정의 : 

두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n > n0에 대하여 |f(n)>=c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=Ω(g(n))이다.

 

 

빅세타 표기법 :

어떤 함수의 상한과 하한을 표시하는 방법

 

빅세타 표기법 정의 : 

두 개의 함수 f(n)과 g(n)이 주어졌을 때 모든 n > n0에 대하여 c1|g(n)|<=|f(n)<=c2|g(n)|을 만족하는 3개의 상수 c1, c2와 n0가 존재하면 f(n)=∂(g(n))이다.

 

 

최선, 평균, 최악의 경우

알고리즘의 효율성은 주어지는 자료집합에 따라 3가지 경우로 나눠서 평가할 수 있음.

 

1. 최악의 경우 (worst case)

자료집합 중에서 알고리즘의 수행시간이 가장 오래 걸리는 경우.

알고리즘의 시간 복잡도 척도로 많이 쓰임.

 

2. 최선의 경우 (best case)

수행시간이 가장 적은 경우.

 

3. 평균의 경우 (average case)

알고리즘의 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려하여 평균적인 수행시간을 의미.

광범의한 자료집합에 대하여 알고리즘을 적용하여 평균값을 계산해야 함.

평균 수행시간 상당히 구하기 힘들 수 있음.

 

예 : 

순차탐색 알고리즘, 비교 연산 seq_search.c

int seq_search(int list[], int key)
{
	int i;
	for (i = 0; i < n; i++)
		if (list[i] == key)
			return i;	//탐색에 성공하면 키 값의 인덱스 반환
	return -1;	// 탐색에 실패하면 -1 반환
}

1. 최악의 경우 (worst case)

찾고자 하는 숫자가 맨 마지막에 있는 경우.

빅오 표기법으로는 O(n)

 

2. 최선의 경우 (best case)

찾고자하는 숫자가 배열의 맨 처음에 있는 경우.

빅오 표기법으로는 O(1)

 

3. 평균의 경우 (average case)

모든 숫자가 균일하게 탐색된다고 가정.

모든 숫자들이 탐색될 가능성 : 1/n.

모든 숫자들이 탐색되었을 경우의 비교 연산 수행 횟수를 더한 후, 전체 숫자 개수를 나누어주면 평균적인 경우의 비교 연산 수행 횟수를 알 수 있음.

(1 + 2 + ... + n)/n = (n+1) / 2

빅오 표기법으로는 O(n).

 

 

Quiz

01. 다음의 시간 복잡도 함수를 빅오 표기법으로 표시하라.

1. 9n^2 + 8n + 1  →  O(n^2)
2. n! + 2^n  →  O(n!)
3. n^2 + n log_2 n + 1  →  O(n^2)
4. sum _{i=1} ^{n} i ^{2}  →  O(n^4)