(CLRS) 알고리즘의 역할

2020, Apr 10    

• 알고리즘 글 목록

• 이 글은 CLRS(Introduction to algorithm) 책을 요약한 것이므로 자세한 내용은 CLRS 책을 참조하시기 바랍니다.

알고리즘

• 먼저 알고리즘의 정의에 대하여 정리해 보겠습니다.
• 알고리즘은 주어진 문제를 풀기 위해 잘 정의된 단계적인 절차로 입력을 출력으로 변환하는 일련의 계산 과정입니다.
  • 입력 : 1개 이상의 입력이 존재해야 합니다.
  • 출력 : 1개 이상의 출력이 존재해야 합니다.
  • 명확성 : 각 명령어의 의미는 모호하지 않고 명확해야 합니다.
  • 유한성 : 한정된 수의 단계 후에 반드시 종료해야 합니다.
  • 유효성 : 모든 명령어는 실행할 수 있는 연산이어야 합니다.
• 알고리즘을 제시할 때에는 그 알고리즘의 타당성이 입증되어야 하고 그 알고리즘의 효율성 분석이 이루어져야 합니다.

알고리즘의 효율성

• 알고리즘의 효율성을 기술할 때에는 성능 측정의 관점과 성능 분석의 관점으로 나누어서 생각해 볼 수 있습니다.
• 먼저 성능 측정의 관점에서는 반드시 알고리즘 구현이 필요합니다.
• 입력의 갯수가 \(n\) 개일 때, A라는 알고리즘은 \(n^{2}\) 초가 걸리고 B라는 알고리즘은 \(2^{n}\)초가 걸린다고 가정해 보겠습니다.
• 이 때, \(n = 4\)이면 알고리즘 A와 B 모두 16초가 걸리지만 \(n = 100\)이라면 알고리즘 A는 10000초 이지만 B는 \(2^{100}\)초가 걸립니다.
• 이것을 실제 코드로 구현해 보고 수행 시간을 측정하여 성능을 측정하는 것이 성능 측정 방법입니다.
• 이 방법의 한계는 하드웨어에 따라(컴퓨터, 임베디드…) 시간이 다르게 측정될 수 있고 심지어 어떤 소프트웨어(C, C++, python)를 이용하여 코드를 구현하였는 지에 따라서도 시간 측정이 달라 질 수 있다는 한계가 있습니다.
• 따라서 만약 성능 측정을 하였다면 하드웨어와 소프트웨어 환경을 반드시 적어주어야 합니다.

• 반면 성능 분석은 구현이 불필요 하여 많은 연구자들이 이 방법을 이용하고 있습니다.
• 성능 분석을 할 때에는 시간 복잡도와 공간 복잡도를 통하여 나타내고 특히 알고리즘의 성능 분석은 시간 복잡도에 중점을 둡니다.
• 시간 복잡도는 입력 수 (n)에 따른 연산의 실행 횟수를 나타냅니다.

• 알고리즘 글 목록