[알고리즘] 알고리즘 수업내용정리

알고리즘 : 문제를 해결 하는 방법, 추상적, 개략적으로 기술한 조리법

알고리즘을 구체적으로 표현한 것이 프로그램이다.

* 알고리즘의 정확성 (Correctness)

허용된 입력에 대해서 제대로 동작해야 함

정확히 우리가 기대하는 것을 수행해야 함

* 프로그램 오류

1) 문법 오류 (Syntax Error)

- 명령문 끝에 세미콜론 등

2) 의미상의 오류 (Semantic Error)

- 2 * 5 와 2 ** 5 

3) 논리적인 오류 (Logical Error, Algorithmic Error)

- 가장 치명적인 오류

* 부정확한 알고리즘 결과

- Abort (Abnormal Termination)

- 무한 루프 (Infinite Loop)

- 정상적으로 끝났지만 잘못된 결과를 출력

* 시간 복잡도 분석

- 하드웨어 환경에 따라 처리시간이 달라진다. (부동소수 처리 프로세서 존재 유무, 나눗셈 가속 기능 유무, 입출력 장비의 성능)

- 소프트웨어 환경에 따라 처리시간이 달라진다. (프로그램 언어의 종류, 운영체제, 컴파일러의 종류)

- 이러한 환경적 차이로인해 분석이 어렵다.

* 알고리즘의 실행시간

- 효율분석은 항상 최악의 경우(Worst Case)를 기준으로 말함

- 무작위로 분포하기 때문에 평균적인 경우를 정의하기 어려움

- 최악의 데이터가 들어오더라도 이 시간이면 실행한다고 말하는 것이 안전