알고리즘은 문제를 해결하기 위한 방법을 추상화하여 일련의 단계적 절차를 논리적으로 기술한 명세서이다.
예를 들어, 요리 레시피도 알고리즘의 하나라고 할 수 있다.
표현 방식
알고리즘을 표현할 때, 다음과 같은 방식이 있다.
- 자연어
사람이 사용하는 언어로 서술 - 순서도(Flow Chart)
순서도의 작성 규칙에 따라 도식화
- 프로그래밍 언어
- 가상 코드(Pseudo code)
성능분석
알고리즘을 분석, 판단하는 기준으로 정확성, 명확성, 수행량, 메모리 사용량, 최적성 등이 있다.
이 중 가장 중요한 항목은 최적성이며, 알고리즘을 적용할 시스템의 사용 환경에 따라 수행량과 메모리 사용량이 달라지기 때문에 가장 좋은 알고리즘이란 최적의 알고리즘이라고 할 수 있다.
성능 분석 방법
성능 분석 방법은 공간 복잡도와 시간 복잡도, 일반적으로 이 두가지를 평가한다.
- 공간 복잡도 (Space Complexity)
프로그램을 실행하여 완료하기 까지 필요한 저장 공간을 의미한다.
따라서 필요한 고정 공간 + 가변 공간으로 계산된다. - 시간 복잡도 (Time Complexity)
프로그램을 실행하여 완료하는데 걸리는 시간이다, 컴파일 시간 + 실행 시간의 합으로 표현한다.
일반적으로 빅-오(Big Oh) 표기법을 사용하여 표기한다.
빅-오(Big Oh) 표기법
① 빅-오 표기법은 실행 빈도수를 구하여 실행 시간 함수를 찾고, ②가장 큰 영향을 주는 n에 대한 항을 선택하여, ③ 계수는 생략하고 O의 오른쪽 괄호 안에 표시한다.
알고리즘에 따라 표현되는 예시는 다음과 같다.
logn, n, nlogn, n², n³, 2ⁿ...
=> O(logn), O(n), O(nlogn), O(n²), O(n³), O(2ⁿ)...
<<참고 자료>>
이지영, "C로 배우는 쉬운 자료구조 (개정판)", 한빛아카데미, 2013년, p63 ~ p77