[02]알고리즘의 성능분석

• 알고리즘의 공간복잡도 ( space complexity )

" 어떤 알고리즘이 메모리는 적게 쓰는가 ? "

그러나 메모리의 사용량은 알고리즘의 성능에 크게 영향을 미치지않는다.

따라서 알고리즘을 평가할때는 아래에 나오는 시간복잡도가 더 중요하다.

• 알고리즘의 시간복잡도 ( time complexity )

" 어떤 알고리즘이 더 빠른가 ? "

• 시간복잡도를 평가하는 방법

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

위 그래프에서는

데이터가 적을 때는 빨간색 알고리즘이 더 빠르다.

그러나 데이터가 많아지면 초록색 알고리즘이 더 빠르다.

때문에 알고리즘은 상황에 맞게 판단해서 구현해야한다.

• T(n) 을 구하는 방법

for(i=0; i<len;i++){

if(ar[i]==target) return i;

}

1. 핵심이 되는 연산자를 찾는다.

위 알고리즘에서 어떤 연산자가 핵심일까 ? ( 어떤 연산을 적게 수행하는 알고리즘이 좋은 알고리즘일까?)

답은 == 연산이다. 다른연산자 ( <, ++ ) 의 경우 ==연산에 의존적이다.

2. 최선의 경우(best case) vs 최악의 경우(worst case)

위 알고리즘에서 운이 좋은경우 내가 찾고자하는 target이 배열의 맨앞에있어 연산횟수가 1이 된다.

이 경우를 최선의 경우라고 한다.

반대로 운이 나쁜경우 target이 배열의 맨끝에 있어 연산횟수가 데이터의 수인 n이 된다.

이 경우를 최악의 경우라고 한다.

위쪽의 그래프에서 볼 수 있듯이 데이터가 작은 경우에는 성능에 크게 차이가 없지만,

데이터가 많은 경우에는 성능의 차이가 커진다.

따라서, 알고리즘의 성능을 판단하는데에는 최악의 경우가 더 중요하다.

3. 최악의 경우로 T(n)을 계산

위 알고리즘의 T(n) = n

• Big-Oh 표기법

함수 T(n) 에서 영향력이 가장 큰 부분이 어디인가?

 

이때 n이 증가함에 따라 영향력이 가장 큰 부분은 n^2 이다.

나머지 2n , 1 등이 미치는 영향은 미미해지므로

위 식의 빅오는   이며, 이는 두가지 해석이 가능하다. 

1. 데이터 수의 증가에 따른 연산횟수의 증가 형태를 좌표평면에 그리면, 증가하는 추세가 

 

과 유사한 형태를 띈다.

2. 아무리 데이터가 증가해봤자 증가율의 패턴이

 

을 넘지 못한다.

※ T(n) 이 다항식으로 표현된 경우 최고차항의 차수가 빅오이다.

• 대표적인 Big-Oh

     : 상수형 빅오

 데이터 수에 상관없이 연산횟수 고정.

 ex) 데이터 수에 상관없이 연산을 100번해도 O(100) 이 아닌 O(1) 이라 쓴다.

: 로그형 빅오

 데이터 수의 증가율에 비해 연산횟수의 증가율이 훨씬 낮다.

 아주 좋은 알고리즘이다.

: 선형 빅오

 데이터 수와 연산횟수가 비례한다. 

 ex) T(n) = 2n+1

: 선형로그형 빅오

 데이터의 수가 2배로 증가하면, 연삿횟수는 2배를 조금 넘게 증가한다.

: 데이터 수의 제곱에 해당하는 연산이 필요하다.

 데이터양이 많아지면 성능이 나쁜 알고리즘이다.

이중 중첩 반복문에서 많이 발생한다.

: 지수형 빅오

 5번보다 훨씬 더 사용하기에 무리가 있는 알고리즘.

 지수적 증가는 매우 큰 연산횟수의 증가를 보인다.

연산횟수를 비교하자면

                 

   ←성능이 좋음                                                                             성능이 나쁨→

• Big-Oh의 수학적 판별법 ( 나중에 추가예정 )

두 개의 함수 f(n) 과 g(n)이 있을 때, 모든   에 대하여 을 만족하는 두개의 상수 C와 k 가 존재하면 f(n) 의 빅오는 O(g(n))이다.