알고리즘 분석

알고리즘의 가장 중요한 기본 성질은 "어떤 주어진 문제의 해결 능력"이다. 알고리즘의 성능을 분석하기 위한 기준으로 다음과 같은 요소들을 참고할 수 있다.

1. 정확성(correctness)

2. 수행량(amount of work done) = 시간 복잡도(time complexity)

3. 사용공간(amount of space used) = 공간 복잡도(space complexity)

4. 단순성(simplicity)

5. 최적성(optimality)

1. 정확성

정확성이란 "알고리즘이 타당한 입력이 주어졌을 때 유한 시간 내에 계산이 수행되어 올바른 결과를 출력하는 것"이라고 정의할 수 있다.

정확성을 증명하는 방법으로는 수학적 귀납법이다. 특히 수학적 귀납법은 알고리즘 내의 루프가 의도한대로 수행 되는지를 증명하는데 사용된다. 귀납법을 간단히 설명하면 다음과 같다.

수학적 귀납법

명제 P(n)이 모든 자연수 n에 대하여 성립하는 것을 증명하려면 다음 두 가지를 증명하면 된다.

(1) n = 1일 때, 명제 P(n)이 성립한다.

(2) n = k일 때, 명제 P(n)이 성립한다고 가장하면 n=k+1 일 때에도 명제P(n)이 성립한다.

위와 같이 임의의 자연수에 대하여 참임을 증명하는 방법을 수학적 귀납법이라 한다.

2. 수행량

알고리즘에 의하여 수행되는 작업의 양, 즉 시간은 어떻게 측정될 수 있을까? 이는 알고리즘들을 효과적으로 분석할 수 있는 기준으로 선택되어야 한다.

알고리즘의 분석을 위해 가장 필요한것은 "어느 알고리즘에서든 사용되는 연산자가 아니라 그 알고리즘에서 가장 중요한 연산이 무엇인가?" 이다. 따라서 중요한 연산들로만 그 수행량을 측정한다면 효과적으로 수행량을 비교할 수 있을 것이다. 이 때 선택된 연산을 기본연산(basic operation)이라 한다.

기본연산은 알고리즘에 의해 수행되는 연산중에서 가장 기본이되고 가장 중요한 연산으로 선택되는 연산자를 말한다. 따라서 기본연산은 작업의 양을 계산하는데 효과적인 측정 단위가 된다.

3. 사용 공간

알고리즘의 사용 공간이라고 하는 것은 알고리즘이 수행되기 위해 필요로 하는 메모리공간을 말한다. 알고리즘의 수행에 필요로 하는 공간으로는 고정적으로 요구되는 공간과 가변적으로 요구되는 공간으로 나누어 생각할 수 있다.

고정적으로 요구되는 공간은 프로그램의 코드들이 저장되는 명령어 저장공간(code section)과 단순 변수나 구조체 변수, 상ㅅ들이 저장될 수 있는공간(data section)으로 볼 수 있다.

가변적인 공간은 특정 입력에 따라 가변적으로 요구되는 공간(heap) 등을 말한다.

따라서 공간의 복잡도를 측정하는 방법은 고정적으로 요구되는 공간을 제외하고, 가변적으로 요구되는 공간들을 계산하여 공간복잡도로 정의하고 있다. 공간복잡도는 특정 입력에 따른 최악의 경우와 평균의 경우로 측정하여 비교 분석된다.

4.단순성

알고리즘에 있어 단순성이란 알고리즘의 정확성 증명과 알고리즘에 대한 프로그램의 작성과 디버깅 , 수정을 더 쉽게 한다.

5. 최적성

어떤 특정 문제를 해결하기 위해서는 얼마나 많은 연산들이 필요한 것일까? 알고리즘의 복잡도를 분석하여 성능이 가장 좋은 알고리즘을 찾을 수 있을까? 알고리즘의 "최적의 알고리즘이다"라고 하는 것은 "최소의 수행량으로 더 적은 수행량을 갖는 알고리즘은 없다"는 것을 의미한다 즉, 더 적은 기본연산으로 수행될 수 있는 알고리즘이 없다면 알고리즘은 Optimal 하다 라고말하는 것이다.

n개의 원소로 구성된 리스트에서 가장 큰 원소를 찾는  알고리즘

int FindMax(int *list, n){

int i, max = list[0];

for(i=0;i<n;i++)

if(max < list[i]) max = list[i];

return max;

}

분석

알고리즘의 기본 연산은 비교 연산이다. 이 비교연산은 5번 행에서 수행된다. 이 때 수행되는 횟수는 n-1번이 된다. 따라서 최악의 경우 최대값을 찾는데 n-1번의 비교연산이 필요 한것이다. 

최악의 경우인 W(n) = n-1 이 된다

하한을 찾기 위하여 리스트내의 모든 원소가 서로 다르다고 가정해보자 이 때, n개의 원소들 중 n-1개는 명확히 최대값이 될 수 없다. 따라서 어떤 원소든지 자신보다 큰 원소를 하나만 갖는다 하더라도 최대값이 될 수 없다 따라서 비교하는 명령인 5행에서 n-1개의 원소는 반드시 더 작게 되고 이는 n-1번의 비교를 통하여 매번 작다라는 결과가 나오게 되고, 이는 적어도 n-1번의 비교 연산이 발생하게 되는 것이다. 이때 정의되는 하한인 F(n)=n-1이된다.

결론적으로 W(n) = F(n)이 됨으로써 이 알고리즘을 최적의 알고리즘으로 판단할 수 있는 것이다. 

만일 W(n) ≠ F(n)과 같은 결과가 나온다면 더 좋은 최적의 알고리즘이 존재함을 의미하게 된다.

출처: http://ph4nt0m.xyz/111 [Phantom]