1.2 알고리즘의 성능 분석

알고리즘 성능 분석하는 이유

1. 최근 상용 프로그램의 규모가 이전에 비해서는 엄청나게 커지고 있기 때문이다.

2. 사용자들이 점점 빠른 프로그램을 선호한다.

수행시간 측정방법

단순하지만 확실한 방법은 알고리즘을 프로그래밍 언어로 작성하여 실제 컴퓨터상에 실행시킨 다음, 그 수행시간을 측정하는 것이다. 하지만 이 방법은 몇 가지 문제가 있다.

 

1. 알고리즘이 복잡한 경우에는 구현해야 된다는 큰 부담이 될 수 있다. 

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

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

4. 컴퓨터 언어에 따라 수행 시간이 달라질 수 있다.

 

알고리즘 복잡도 분석 방법

알고리즘 복잡도 분석

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

 

시간 복잡도 함수

알고리즘의 절대적인 수행 시간을 나타내는 것이 아니라 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지를 숫자로 표기한다.

- 보통 프로그램에 주어지는 입력의 개수 n에 따라 변하게 된다.

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

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

 

ex)

알고리즘	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
대입연산	1	n	n*n
덧셈연산		n	n*n
곱셈연산	1
나눗셈연산
전체연산수	2	2n	2n^2

 

빅오 표기법

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

정의

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

많이 쓰이는 빅오 표기법

O(1) : 상수형

O(log n) : 로그형

O(n) : 선형

O(nlog n) : 선형로그형

O(n^2) : 2차형

O(2^n) : 지수형

O(n!) : 팩토리얼형

 

O(1) < O(log n) < O(n) < O(nlog n) < O(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))이다. ( n0는 상수이다.)

빅세타는 동일한 함수로 상한과 하한을 만들 수 있다.

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

 

최선, 평균 최악의 경우

최악(worst case) : 자료집합에 중에서 알고리즘 수행시간이 가장 오래 걸리는 경우

최선(best case) : 수행시간이 가장 적은 경우를 의미한다.

평균적인 경우(average case) : 알고리즘의 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려하여 평균적인 수행시간을 의미한다.