2. 알고리즘 복잡도 분석

Dn

입력된 값의 크기

 

I

Dn에서의 특정 원소

 

t(I)

The number of basic operations

 

p(I)

입력값 I의 발생 확률

 

Average case

A(n) = ∑ p(I)t(I)

평균 basic operations 작업 수

 

Worst case

W(n) = max { t(I) | I ∈ Dn }

최대 기본 작업 수(입력이 가장 안좋은 케이스 일 때)

 

 

알고리즘 평가 기준 5가지

1. Correctness

--> 올바름, 정확성

 

2. Simplicity

--> 간단, 명료

 

3. Optimality

--> 최적

 

4. Amount of space used

--> Memory

 

5. Amount of work done

--> Time( W(n) 사용 )

 

 

 

시간을 비교하여 좋은 알고리즘을 찾을 때

 

- Best case(최상)

- Average case(평균)

- Worst case(최악)

 

위와 같은 분석 방법이 있는데

대부분 Worst case = W(n) 최악 분석을 사용한다.

 

그렇다면 왜 최악 분석을 사용할까?

1. 많은 알고리즘들이 대부분의 실행에서 최악의 성능을 보인다.

2. 최상의 경우는 똑같은 성능을 보인다.

3. 평균 성능을 계산하는 것이 쉽지 않다.

4. 최악의 경우는 성능의 상위 한계(upper bound)를 의미한다.

--> 상위 한계를 쉽게 예를 들자면 상한선 느낌이다. 그 이상에 케이스는 나오지 않는다.