알고리즘의 성능 분석방법

핵심

1. 시간복잡도를 중심으로 최악의 경우를 판단하여 알고리즘의 성능을 분석한다.

2. 연산의 중심이 되는 연산자의 연산횟수를 계산해서 T(n)함수를 그래프로 나타낸다.

알고리즘을 평가하는 두가지 요소

- 시간복잡도(time complexity)

 -> 얼마나 빠른가?

- 공간복잡도(space complexity)

 -> 얼마나 메모리를 적게 사용하는가?

 

두개중 시간 복잡도를 더 중요시 한다고 한다.

 

시간 복잡도의 평가방법

- 중심이 되는 특정 연산의 횟수를 세어서 평가를 한다.

- 데이터 수에 대한 연산 횟수의 함수 T(n)을 구한다.

-> 함수를 그려놓으면 그래프로 볼 수가 있게 된다.

-> 데이터가 늘어남에 따라 연산횟수가 얼마나 늘어나는지가 정말 중요하기 때문에 T(n)을 구한다.

 

알고리즘의 수행 속도 비교 기준

- 데이터의 수가 적은 경우 수행 속도는 큰 의미가 없다.

- 데이터의 수에 따른 수행 속도의 변화 정도를 기준으로 한다.

 

** 주변 연산자들의 연산횟수는 중심이 되는 연산자의 연산횟수에 의존적이라는 특징을 기억하면 어떠한 연산자의 연산횟수를 세어야 할지가 보인다.

 

최악의 경우와 최상의 경우

1. 최상의경우 : 배열의 맨 앞에서 대상을 찾는경우 

2. 최악의 경우 : 배열의 끝에서 찾거나 대상이 저장되지 않은 경우

* 우리는 최악의 경우를 성능평가의 척도로써 본다.

 

평균적인경우

1. 가장 현실적인 경우이지만 계산하기가 어렵고 객관적 평가가 쉽지 않다.

- 연출이 어렵다

- 증명이 어렵다.

- 상황에 따라 달라진다.