알고리즘 분석 방법

실행 시간(Running Time)

- 대부분의 알고리즘은 입력 객체를 출력 객체로 변환함.

- 알고리즘의 실행 시간은 보통 입력 객체의 크기에 따라 증가함.

- 평균 case time을 결정하는것이 어려운 편.

- 그래서 실행시간의 최악의 경우(worst-case)에 집중함. ( 분석을 더 쉽게 하기 위해서 )

 

실험 연구(Experimental Studies)

- 알고리즘을 실행하는 프로그램을 작성하는 것.

- 다양한 입력 크기와 구성으로 프로그램을 실행함.

- clock()과 같은 메소드를 사용하여 실제 실행 시간을 정확하게 측정함.

 

실험 연구의 한계

- 어떤 것이 알고리즘을 실행하는데 반드시 필요한 것인지 알기 어려움.

- 결과가 다른 입력들을 포함하지 않은 실행 시간을 나타내는지 알기 어려움.

- 두 가지 알고리즘을 비교하기 위해선, 같은 하드웨어와 소프트웨어의 실행 환경이 요구됨.

 

이론 분석(Theoretical Analysis)

- 알고리즘을 직접 실행하는 대신, high-level(기계어)로 설명하는 방법을 사용하는 것.

- 모든 가능한 입력 case를 고려함.

- 독립적인 하드웨어 / 소프트웨어 환경에서 알고리즘의 속도를 평가하도록 만듦.

 

의사(슈도) 코드(Pseudocode)

- 알고리즘의 high-level 설명.

- 영어 문장보단 구조화된 언어.

- 프로그램보단 덜 세부적임.

- 알고리즘을 설명하는데 선호되는 표기법.

- 프로그램의 design issue를 숨김.

 

EX) 배열에서 원소의 최대값을 찾는 알고리즘을 슈도코드로 표현하면 ?

Algorithm arrayMax(A,n)
	Input array A of n integers
    Output maximum element of A
    currentMax<- A[0]
    for i<-1 to n-1 do
    	if A[i] > currentMax then
        	currentMax<- A[i]
    return currentMax

Primitive Operations

- 알고리즘에 의해 수행되는 기본적인 연산.

- 슈도코드 안에서 식별 가능함.

위에 표기된 배열의 최대값의 원소를 찾는 알고리즘에선

currentMax<- A[0]                2

for문                                   2n

조건문                                 2(n-1)

currentMax<- A[i]                 2(n-1)

return                                 1

모두 다 합친 Total          =     6n-1이다.

 

빅오 표기법(Big-Oh Notation)

- 함수 f(n)과 g(n)이 있을 때, f(n)이 O(g(n)) 이라고 가정하자. 양수인 c와 첫째항 n0은

f(n) <= cg(n) for n>=n0 의 관계를 갖는다.

- 빅오 표기법은 가능한 작고 간단하게 표현해야 한다.

EX ) 2n is O(n^2)이 아닌 2n is O(n)

    ) 3n+5 is O(3n)이 아닌 3n+5 is O(n)

 

점근 분석(Asymptotic Analysis)

- 점근 분석이란 빅오 표기법으로 알고리즘의 실행 시간을 분석하는 것을 말함.

- 실행되는 알고리즘의 primitive operations의 worst-case를 찾고, 그것을 빅오 표기법으로 나타냄.

위 arrayMax 알고리즘을 예시로 들면 primitive operations = 6n-1 이므로 따라서 O(n)이다.

 

누적 평균(Prefix Averages)

- 크기가 n인 순열이 있을 때, 처음부터 현재 요소까지의 평균을 구하는 알고리즘.