[알고리즘] 18. 알고리즘 성능

공부한 날짜: 2021. 11. 07

 

-알고리즘 성능 분석 요소 5가지 

(1) 정확성: 정확하게 작동하는가?

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

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

(4) 단순성: 얼마나 단순한가?

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

 

-알고리즘 수행 시간의 분석

적절한 알고리즘 수행시간: 컴퓨터의 성능에 관계 없이 명확하게 정의될 수 있어야하며, 이미 알려진 수행 시간을 바탕으로 입력데이터의 크기의 변화에 대한 수행시간의 변화를 예측할 수 있어야함 

(1) 최악의 경우: 최대 걸리는 시간(상한선)-> 어떤 환경에서도 실행되었을 때 기본으로 걸리는 시간 

(2) 평균의 경우: 일반적인 상황에서 소요되는 알고리즘 수행시간

(3) 최선의 경우: 최적의 상황에서 소요되는 알고리즘 수행시간(적절하지 않음, 매번 최적의 상황으로 동작하는게 아니므로)

 

1. 점근 표기법

: 알고리즘의 수행 시간을 대략적으로 나타내는 방법(수행시간 식의 최고차 항으로만 성능 대략적으로 표시)

장점: 알고리즘의 성능을 단순화해서 표현 -> 알고리즘 간의 성능 비교가 용이 

 

종류: O(Big O)표기법, Ω(Big Omega)표기법 , Θ(BigTheta)표기법 

(1) O(Big O)표기법 : 수행시간 상한을 나타낼 때 사용함 

(2) Ω(Big Omega)표기법 : 수행시간의 하한을 나타낼 때 사용함 

(3) Θ(BigTheta)표기법 : 알고리즘 수행시간의 상한과 하한을 동시에 나타냄 

 

2. 재귀 알고리즘의 성능 분석 

 

-재귀 방정식: 자기 자신을 항으로 갖는 방정식

재귀 알고리즘의 수행시간(성능)을 나타내는 또 하나의 표현방법이다