알고리즘 (Algorithm)

알고리즘

정의

• 문제를 해결하는 단계적 절차 또는 방법
• 어떤 값이나 값의 집합을 입력으로 받아 또 다른 값이나 값의 집합을 출력하는 잘 정의된 절차

알고리즘을 설계하기 위해서 우선 '해야 할 작업을 명확하게 명시'해야 한다.
설계하려는 알고리즘이 '무엇을' 하는지는 입력과 출력으로 명시할 수 있다.

조건

1. 정확성
   • 알고리즘은 주어진 입력에 대해 올바를 해를 주어져야 한다.
2. 수행성
   • 알고리즘의 각 단계는 컴퓨터에서 수행 가능하여야 한다.
3. 명확성
   • 수행할 작업의 내용과 순서가 이해하기 쉽고, 간명하게 기술되어야 한다.
4. 유한성
   • 알고리즘은 일정한 시간 내에 종료되어야 한다.
5. 효율성
   • 알고리즘은 효율적이어야 한다.
   • 수행시간이 짧을수록 좋다.

표현방법

1. 자연어
2. 의사코드(pseudo code)
3. 순서도

알고리즘의 분석

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

• 시간 복잡도 -> 얼마나 빠른가?
• 공간 복잡도 -> 얼마나 메모리를 적게 쓰는가?
  (일반적으로 "시간 복잡도"를 더 중요시 함)