1. 알고리즘 성능 측정 기준과 수행 시간

알고리즘 성능 측정 기준

정확성 : 정확하게 동작하는가?

=> 알고리즘이 입력값에 대해 정해진 절차를 수행하여 결과적으로 정확한 출력을 제공하는가를 가리키는 기준

 

작업량 : 얼마나 적은 연산을 수행하는가?

=> 요구되는 기능을 수행하기 위해 알고리즘이 수행해야 하는 작업의 양이 얼마나 되는가를 가리키는 기준

ex) 버블 정렬에서 정렬을 수행하기 위해 비교 연산을 몇 번 수행하는가? 라는 질문에서 '비교횟수'

 

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

=> 말 그대로 해당 알고리즘이 작업을 수행할 때 사용해야 하는 메모리의 양

 

단순성 : 얼마나 단순한가?

=> 알고리즘을 짤 때는 보기쉽고 단순해야 한다

 

최적성 : 더 이상 개선할 여지가 없을 만큼 최적화가 되어있는가?

=> 최적화를 거친 알고리즘들은 이해하기 어렵다

=> 최적의 성능을 위해서는 개선 가능한 모든 요소 (작업량, 메모리 사용량 등)을 쥐어짜야 한다

---

알고리즘 수행 시간 분석

알고리즘 수행 시간 (Time Complexity)

=> 어떤 프로그램이 시작하여 종료되기까지 걸리는 시간 길이

(하드웨어에 의존하지 않고 정의될 수 있어야 하며, 필요한 경우 이미 알려진 수행 시간을 바탕으로 입력 데이터의 크기 변화에 대한 성능 변화 계산이 가능해야한다)

 

알고리즘 수행 시간의 목표

1. 최악의 경우

알고리즘을 사용하는 어떤 경우에도 보장되는 알고리즘의 성능을 의미한다

 

2. 평균의 경우

일반적인 상황에서의 알고리즘 수행 시간을 의미

 

3. 최선의 경우

가장 좋은 조건이 주어졌을 때의 알고리즘 수행 시간