[알고리즘 설계와 분석] 알고리즘 정의와 성능 분석

 

[알고리즘 설계와 분석] 알고리즘 정의와 성능 분석

 

○ 알고리즘(Algorithm) 의미

---

    - 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것.

    - 주어진 문제를 효율적으로 풀기 위한 방법을 단계별로 기술해 놓은 것.

    - 알고리즘을 설계하기 위해서는 해야할 작업을 명확하게 명시해야 함.

 

 

○ 알고리즘의 조건

---

    - 입력: 0개 이상의 입력이 존재해야 함.

    - 출력: 1개 이상의 출력이 존재해야 함.

    - 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 함.

    - 유한성: 한정된 수의 단계 후에는 반드시 종료되어야 함.

    - 유효성: 각 명령어들은 실행 가능한 연산이어야 함.

 

 

○ 알고리즘의 기술

---

    - 영어나 한국어 같은 자연어

    - 흐름도 (flow chart)

    - 유사 코드 (pseodo-code)

    - 프로그래밍 언어

 

 

○ 알고리즘의 분석

---

    4단계로 구성되는데, 각 단계는 문제 정의, 알고리즘 설명, 정확성 증명, 성능 분석.

     

    - 문제 정의(Problem Definition): 해결하고자 하는 문제. 현실 세계의 문제를 컴퓨터를 이용하여 풀 수

                                                있도록 입력과 출력의 형태로 정의.

    - 알고리즘 설명(Algorithm Description): 문제를 해결하기 위한 단계를 차례대로 설명.

                                                          수도 코드(Pseudo code) 등으로 표현.

    - 정확성 증명(Correctness Proof): 주어진 알고리즘을 수행했을 때 문제를 해결할 수 있는지 증명.

                                                 항상 올바른 답을 내고 정상적으로 종료되는지 증명.

    - 성능분석(Performance Analysis): 문제를 해결하기 위해 필요한 시간이나 공간들이 얼마나 되는지 비교. 

                                                  수행시간이나 사용 공간에 대한 알고리즘의 성능을 비교하기 위한 분석.