01-2. 알고리즘 복잡도

1. 알고리즘

유한한 단계를 통해 문제해결 절차 및 방법

 

예) 1~100 합

1. 1 + 2 + 3 + ...

2. 100 * (1 + 100) / 2 = 5050 => 이런 해결 방법을 절차적으로 정리한것.

 

알고리즘을 효율적이어야 한다.

> 입력이 커질 수록 효율에 따라 실행시간 차이 발생

 

알고리즘 설계 -> 실행 필요한 지원분석 -> 효율성 제시

 

효율성 -> 복잡도. 복잡도가 높을 수록 효율성 저하.

1. 공간 복잡도

2. 시간 복잡도

 

시간 복잡도

입력 크기에 대한 함수로 표기. 점근적 표기를 사용한다. 입력 n이 무한대로 커질 때를 가정.

1. 빅오, 2. 오메가, 3. 세타

 

빅오표기법 - worst case

점근적 상한을 의미한다. 

O(g(n)) = f(n)이라는 것은 g(n)이 모든 n에 대해서 항상 f(n)보다 크다는 뜻이다.

 

오메가표기법 - best case

점근적 하한을 의미한다.

오메가(g(n)) = f(n)이라는 것은 f(n)은 최소 g(n)보다 크다.

 

세타표기법 - average case

빅오와 오메가표기가 같은 경우에 사용한다.

세타(g(n)) = f(n) : g(n)과 f(n)은 거의 비슷

 

1 < logN < N < NlogN < N^2 < N^3 < 2^N

 

효율적인 알고리즘 필요한 이유

10억개 데이터 정렬 

	O(n^2)	O(nlogn)
일반 PC	300년	5분
슈퍼컴퓨터	1주일	1초

효율적인 알고리즘은 슈퍼컴퓨터보다 더 가치가 있다.

값비싼 h/w기술개발보다 효율적인 알고리즘 개발이 더 경제적이다.