C 로 구현한 알고리즘 - 1부 준비, 4장 알고리즘 분석

이번엔 4장 알고리즘 분석 복습...

아마도 '재귀' 알고리즘 이후에 알고리즘 분석 챕터가 있는 것은,

이 챕터를 좀 더 이해하기 쉽게 하기 위해서인가 보다.

그렇다 하더라고 학교 수업에 들었던 기억을 떠 올리면, 꽤 지루했던게 기억난다.

알고리즘을 사용할 때, 그 알고리즘의 성능을 이해하는 것은 중요하다.

문제를 해결하기 위해 여러가지 알고리즘을 선택할 때도 효율적인 알고리즘을 선택할 수 있고,

(물론 단순히 알고 있어도 도움은 되겠지만, 이해하고 있다면 훨씬 낫겠지...)

또한, 어떻게 적절하게 사용할 것인지 계획을 세우는 데도 도움이 된다.

(책에서는 Garbage Collection 을 예로 들고 있다. 여기에 사용되는 알고리즘은 많은 시간이

 필요하기 때문에, 적당한 순간에만 사용하도록 해야한다. )

최악분석

알고리즘의 최악의 경우에 대한 성능을 분석하는 것이다.

여기에는 4가지 이유가 있는데,

1. 많은 알고리즘이 대부분의 실행에서 최악의 성능을 보인다. 예를들면, 탐색에서 원하는 자료를 찾지 못하는 경우...

2. 많은 알고리즘이 최상의 경우에 똑같은 성능을 보인다.

3. 평균 성능을 계산하는 것이 쉽지 않은 경우가 있다.

4. 최악의 경우는 성능의 상위 한계를 의미한다. 즉 분석 결과보다 더 나쁘게 실행되지는 않는다는 것을 보장한다.

   (내 생각에는 1, 4번이 제일 중요한듯...)

예외적으로 평균 성능을 근거로 해야 하는 경우는 있다. (예를들면, 퀵 정렬 같은 무작위 알고리즘)

O-표기법

이것은 알고리즘의 성능을 정형적으로 표현하는 가장 일반적인 표기법인다.

이것은 알고리즘의 복잡도(complexity)를 표현한다.

자료가 커짐에 따라, 성능이 어떻게 나빠지는지 나타내는지 보여준다고 생각하면 될 듯.

일반적으로 단순하게 아래와 같이 알고리즘의 복잡도를 표시한다.

(실제로는 상수를 포함한 식으로 표시된다. )

( 일반적인 복잡도와 거기에 해당하는 예. 복잡도가 낮은 순으로. n 은 자료의 갯수. )

복잡도	예
O(1)	자료 집합에서 첫번째 항목을 가져오는 것
O(lg n)	자료 집합을 반으로 나누고 그 반을 다시 반으로 나누는 과정을 반복
O(n)	자료 집합을 순회하기
O(n lg n)	자료 집합을 반복해서 둘로 나누고 나뉘어진 반을 순회하는 것
O(n^2)	한 집합의 각 자료에 대해 같은 크기의 다른 집합을 순회하는 것
O(n^2)	집합의 모든 부분집합을 생성하는 것
O(n!)	집합의 모든 순열을 생성하는 것

(증가율을 표한한 그래프. 가로는 n = 자료의 크기, 세로는 T(n) = 알고리즘의 실행 시간을 나타냄.)

* 적절한 그래프 이미지를 찾지 못해 엑셀에서 직접 작업.

  가로/세로 축, 각 그래프 선에 대해서 레이블을 쓰고 싶은데, 옵션을 못 찾겠음.. (없는건지..)

  그냥 복잡도 순서대로 되어 있으니 참고. 그리고 O(1) 과 O(lg n)은 겹쳐서 안보이는 거임.

결론

특이한 경우가 아니면, 현업에서 이미 알려진 알고리즘에 대해서 알고리즘 복잡도를 분석할 이유가 없다.

각 알고리즘에 대해서 어느 정도의 성능을 나타내는가를 알고 있으면 된다고 생각한다.

우리가 할 수 있는것은 저 복잡도 계산에서 과다한 상수를 포함하지 않도록 하여

알고리즘이 효율적으로 동작하도록 하는 정도?

중요한 것은 위에서도 언급했듯이, 적절한 알고리즘을 적절하게 사용하는 것이다.

(적어놓고 나니 애매한데, 어쨌거나 현업에서는 여러가지 변수가 존재하니깐...)