알고리즘에 앞서 용어들
문제 (Problem) : 답을 찾기 위한 질문
매개변수 (Parameter) : 문제에서 언급된 할당되지 않은 변수들
실체 (instance) : 매개변수에 실제 할당된 값
ex) int n = 5; //n은 매개변수, 5는 실체
점근적 표기
점근적 분석 : 입력이 충분히 큰 경우에 대한 분석
점근적 증가율 : 변수의 크기가 충분히 큰 경우에 변수가 커짐에 따라 함수가 증가하는 비율
점근적 표기법 : 점근적 증가율에 대한 표기법
-> 점근적 표기법에서 계수는 중요하지 않다
why? 입력값 n이 작을 때는 함수의 차이가 커 영향이 크지만 n이 커짐에 따라 그 영향이 미미해지기 때문이다.
알고리즘
어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정
알고리즘은 명확하고 효율적으로 설계해야함
의사코드 (Pseudo-code)
알고리즘으로 수행할 절차를 다양한 언어로 간략하게 서술해 놓은 것
알고리즘 성능 분석 방법
- 실험적 분석
- 이론적 분석
1. 실험적 분석 (Experimental analysis)
알고리즘을 소스코드로 구현한 다음, 실제 환경에서 동작시켜 실제 실행 시간 측정
- C언어의 clock() 함수
문제점
-알고리즘을 실제 구현하기까지 시간과 노력이 소모
-성능을 비교 시, 기본적으로 명시된 것들 (하드웨어 사양) 및 다양한 외부 요인들(코딩 스타일, 컴퓨터 외부 환경)로 인해 정확한 비교가 어려움
2. 이론적 분석 (Theoretical analysis)
알고리즘의 수행시간(=성능)을 실제 구현을 통해서가 아니라 high-level에서 이론적으로 기술하는 방법
-시간은 보통 입력 사이즈에 관한 함수로 표현
-이론적 분석을 통해 구한 수행 시간을 `시간 복잡도 (Time Complexity)라고 함
p(´∇｀)q