알고리즘의 요구조건(정의)
알고리즘은 입력, 출력, 명확성, 유효성, 유한성이 요구된다.
◎ 입력 : 알고리즘은 입력값이 0개 이상이어야 한다. 즉 입력값이 없는 알고리즘도 존재한다는 의미이다.
◎ 출력 : 알고리즘은 출력값이 1개 이상이어야 한다.
◎ 명확성 : 수행 과정은 명확해야 하고 모호하지 않은 명령어야 한다.
◎ 유효성(효율성) : 알고리즘은 실행가능하여야 한다.
◎ 유한성(종결성) : 알고리즘은 반드시 종료되어야 한다. 유한성은 알고리즘과 프로그램의 차이이다. 알고리즘은 종료되어야 하지만 프로그램은 종료되지 않아도 된다.
알고리즘의 분석(복잡도와 복잡도의 표기법)
컴퓨터공학에서는 알고리즘을 얼마나 빠르고, 메모리가 적게 소모되는지를 수학적으로 분석한다.
분석방법은 시간복잡도와 공간복잡도로 나뉜다.
◎ 시간복잡도(time complexity) : 알고리즘(프로그램)이 완료되는데 소요되는 시간의 양
◎ 공간복잡도(space complexity) : 알고리즘(프로그램)이 완료되는데 필요한 메모리 공간의 양
각 복잡도의 표기방법으로는 빅오, 빅오메가, 세타 표기법이 있다.
이를 점근 표기법이라 하는데 대략적인 표기법이라 생각하면 된다.
아래에서 사용할 n은 알고리즘의 단계의 수를 의미하는데 이를 정확하게 계산하는 것은 매우 어렵고 부정확하기 때문에 대략적인 표기법, 즉 점근표기법을 사용하게 된다.
우리는 이 알고리즘의 연산시간이 상수인지, 선형인지, 평방형인지, 지수형인지 등 대략적인 내용만 알면 되기 때문이다.
◎ 빅오(big 'oh')
- 빅오 표기법 정의
- 상한점근, 최악의경우 표기법이라고 한다. 최악의 경우에도 이보다는 빠르다는 것이다. 최악의 경우라는 것은 모든 경우라고도 할수 있기 때문에 신뢰도가 높아 가장 일반적으로 사용되는 표기법이다.
- 대문자 O(오)를 사용하기 때문에 빅오 표기법이라 한다.
- 빅오 표기법 정리(실제 사용하는 방식)
- 예시
◎ 빅오메가(omega)
- 정의
- 하한점근, 최선의경우 표기법
- 로마자 대문자 Ω(오메가)를 사용하기 때문에 빅오메가 표기법이라 한다.
- 정리
◎ 세타(theta)
- 정의
- 상한/하한점근(평균점근)
- 로마자 θ(세타)를 사용하기 때문에 세타 표기법이라 한다.
- 정리
'자료구조, 알고리즘' 카테고리의 다른 글
| [자료구조] 배열(array) (0) | 2018.06.15 |
|---|