알고리즘의 성능

알고리즘의 성능을 가리는 5가지 기준

정확성

알고리즘이 입력 값에 대해 필요한 절차를 정확히 수행하여, 결과적으로 정확한 값을 제공하는가?

작업량

요구되는 기능을 수행하기 위해서, 얼마나 적은 연산을 수행하는가?

ex) 특정 정렬 알고리즘에서 비교연산이 몇번 수행되는지.

메모리 사용량

얼마나 적은 메모리를 사용하는가?

단순성

알고리즘의 정확성 등에 문제가 있을 경우 이를 고쳐야하지만, 복잡한 알고리즘은 분석하기도, 개선하기도 어렵다.

그렇게 때문에 얼마나 단순한지가 중요하다.

최적성

개선가능한 모든 요소(작업량, 메모리 사용량 등)에 대해 더이상 개선할 여지가 없을 만큼 최적화 되어 있는가?

알고리즘의 수행 시간 분석 방법

알고리즘의 효율성을 분석하기위해, 단위 연산이 수행되는 횟수를 입력에 크기에 대한 함수로 구하는 것.

- 시간 복잡도 분석 (Time Complexity Analysis): 입력 크기를 기준으로 단위 연산을 몇번 수행하는지 구하는 것.

- 공간(메모리) 복잡도 분석 (Memory Complexity Analysis): 알고리즘이 메모리 사용면으로는 얼마나 효율적인지를 분석.