[01] Algorithm Analysis (Big-Oh notation)

알고리즘

- 목적) 컴퓨터를 통해 문제를 푼다

- 컴퓨터가 풀 수 있는 문제인지 정의하고(컴퓨터가 쓸 수 있는 형태로 바꾸고), 이 문제(problem)를 컴퓨터가 이해할 수 있도록 명확하고 정확한 절차를 통한 해답(solution)을 찾아나가는 과정이 있어야 함

 

 

문제 : '답을 찾기 위한 질문'

매개변수 : 문제에서 언급되었지만 할당되지 않은 변수들, int x;

실체(instance) : 매개변수에 실제로 할당된 값, x=5;

 

 

알고리즘 : 어떤 문제를 풀기 위한 유한한 절차와 방법

- 문제 : 수학적으로 엄밀히 정의된

- 절차와 방법 : 계산 문제 -> 숫자, 사칙연산 이용    컴퓨터로 계산 문제 -> 컴퓨터에 주어진 명령어 집합(instruction set) 이용

 

 

의사코드 (pseudo-code)

: 알고리즘으로 수행할 절차를 다양한 언어로 간략하게 서술해 놓은 것

 

 

 

알고리즘의 이론적 분석 vs 실험적 분석

 

Big-Oh notation

 

Comparison of Algorithms

 

Algorithm analysis using Big-Oh notation