Azza's Blog

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

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

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

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

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

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

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

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

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

최악분석

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

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

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

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

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

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

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

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

O-표기법

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

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

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

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

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

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

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

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

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

결론

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

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

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

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

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

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

최근에 어떤 계기로 미루고 미뤄왔던 알고리즘 공부를 시작했다.

대학 다닐 때 알고리즘 수업 2번 연속 출석미달로 'F' 받았던터라, 늘 찜찜했는데...

알고리즘을 공부하기 위해 선택한 책은 "C 로 구현한 알고리즘" 이다.

왜냐하면... 나름 오라일리 책인데다가... 회사에 굴러다녀서 살 필요가 없어서...;

대충 1장 소개랑 2장 포인터 다루기는 패스하고

3장 재귀부터 복습 겸 글을 남겨본다.

개본적 재귀(recursion)

문제를 자신보다 점점 더 작은 인스턴스들로 정의할 수 있게 하는 강력한 원리이다.

전산에서는 자신을 호출하는 재귀 함수를 사용해서 재귀적으로 정의된 문제들을 해결한다.

Depth 가 깊어지면 스택 오버플로우의 위험이 크다.

현업에서 실제로 이런 형태를 쓰면 안되겠지.

꼬리 재귀(tail recursion)

컴파일러가 최적의 코드를 만들어 낼 수 있는 재귀의 형태이다.

재귀 호출이 함수 몸체의 제일 마지막에 실행되는 문장이고,

리턴값이 다른식에 사용되지 않는 형태이다.

다시 말해면 재귀함수 호출한 뒤에 수행할 명령이 없어야 한다는거?
(이런 형태는 굳이 Iteration 하게 정의해서 풀 수도 있지만,

 재귀 형태가 머랄까.. 좀 더 문제를 푸는 방법을 명확히 나타내는 듯 하다.

 요새는 컴파일러가 똑똑해져서 최적화 옵션을 주면

 꼬리 재귀도 알아서 Iteration 하게 만들어 준다니깐.. 머.)

팩토리얼 값을 구하기 위한 기본적 재귀와 꼬리 재귀

(빨갛게 표시한 부분을 주목)

따로 부연설명은 하지 않겠다.

주의사항

재귀함수는 반드시! 하나 이상의 종료조건이 있어야 하며,

재귀호출이 이 종료조건에 도달할 수 있어야 한다.

그렇지 않다면 스택 오버플로우~

결론

꼬리 재귀에 대한 좀 더 명확한 이해를 할 수 있었고,

이제 더 정확히 알고 사용할 수 있을꺼 같다.

이상 끝.