[자료구조] 알고리즘 성능 분석 방법

알고리즘 성능을 분석하는 기준에는 정확성, 명확성, 수행량, 메모리 사용량, 최적성 등이 있다. 자료를 입력할 때 유한한 시간 내에 올바른 결과를 출력하는지 알아보기 위한 정확성, 얼마나 이해하기 쉽고 명확하게 작성되었는가를 알아보는 명확성, 기본 연산을 제외한 알고리즘에 사용되는 명령어(연산)들이 수행되는 양을 알아보는 수행량, 사용되는 명령어, 변수, 입출력 자료와 정보를 전달하기 위해 사용하는 메모리 사용량, 가장 최적의 조건을 알아보는 최적성을 통해 설계된 알고리즘의 성능을 분석한다.

---

일반적으로 알고리즘은 실행에 필요한 공간적 측면에서 분석하는 공간 복잡도와 소요 시간 측면의 시간 복잡도를 이용한다. 하지만 최근 큰 용량의 메모리를 저렴하게 구할 수 있어 시간 복잡도(처리 시간)가 컴퓨터 프로그램 성능에 영향을 많이 끼친다.

​

▶ 공간 복잡도: 알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간의 양

 

공간 복잡도 = 고정 공간 + 가변 공간

* 고정 공간: 고정적으로 필요한 저장 공간(프로그램 저장 공간과 변수 및 상수 저장) * 가변 공간: 실행 과정에서 사용되는 자료, 변수, 함수 등을 저장하는 공간

 

---

 

▶ 시간 복잡도: 알고리즘을 프로그램으로 실행하여 완료하기까지의 총 소요시간(수행하는 데 필요한 연산 횟수, 즉 처리해야 하는 요소의 개수가 증가함에 따라 프로그램 규모를 알 수 있으며, 빅-오 표기법을 주로 사용)

 

시간 복잡도 = 컴파일 시간 + 실행 시간

* 컴파일 시간: 프로그래밍 언어를 컴퓨터가 인식 가능한 컴퓨터 언어로 변화하는데 걸리는 시간(프로그램마다 거의 고정적인 시간 소요) * 실행 시간: 명령문의 실행 빈도수에 따라 계산(컴퓨터 성능에 따라 달라질 수 있음)

 

① 빅-오 표기법

- 어떤 알고리즘이 다루게 될 요소(Item)의 개수와 연관된 복잡도(Complexity)를 표현하는 방법

- O(f(n)) 표기, Big Oh of f(n)

- 함수의 상한을 나타내기 위한 표기법으로, 최악의 경우에도 수행 시간 안에는 알고리즘 수행 완료 보장

- 일반적으로 최악의 경우를 고려한 해결책을 찾기 때문에 주로 사용

​

② 빅-오메가 표기법

- Ω(f(n)) 표기, Big Omega of f(n)

- 함수의 하한을 나타내기 위한 표기법으로, 적어도 f(n) 수행 시간 필요

​

③ 빅-세타 표기법

- θ(f(n)) 표기, Big Theta of f(n)

- 상한과 하한이 같은 정확한 차수를 표현하기 위한 표기법

- 정확한 시간 복잡도 계산이 가능할 때 사용

 

 

 

 

참고: 메가존아이티평생교육원, 자료구조 2주 1회