Algorithm Performance evaluation(알고리즘 성능 평가)

 

 

Algorithm Performance evaluation(알고리즘 성능 평가)

---

알고리즘이 주어진 문제를 해결하는데 걸리는 시간과 데이터 입력량의 함수 관계를 해석하는 과정

 

데이터의 입력에 따라 해석하는 시간이 얼마나 걸리는지에 대한 답을 도출.

이를 Computational Comlexity theory(계산 복잡도 이론)에서 Time Complexity(시간 복잡도)라고 하며 일반적으로 알고리즘 성능 평가는 Time Complexity에 대한 평가를 의미.

 

* Space complexity(공간 복잡도 : 메모리를 얼마나 사용하는가) 로 평가하는 방법도 있으나 현대 컴퓨팅 환경에서는 큰 의미가 없음.

 

 

 

 

 

 

 

 

 

알고리즘 평가 기준

 

• 입력된 데이터의 수와 연산 횟수의 함수 관계로 표현
• 데이터의 수와 연산 횟수의 관계를 정확하게 표현하는것은 현실적으로 불가능
• 같은 알고리즘 같은 데이터량도 상황에 따라 다른 결과가 도출됨.
  • Ex) 선형검색

 

 

 

 

 

 

 

 

 

 

 

 

 

 

알고리즘 평가 모델

Time Complexity를 기반으로한 평가

 

• 최악의 경우를 기준.
• 정확도가 아닌 Ordnung(근사치) 측정.
• 그래프 패턴을 평가.
  • x앞의 계수는 상관 없음.

 

 

 

 

이와 같은 평가 모델을 BigO 모델이라 함.

BigO는 계수와 낮은 차수의 수행횟수는 무시한다.

 

• O(1)
  • 데이터가 n만큼 증가 할 때 Time Complexity는 변화 없음 (동일한 상수값)
• O(n)
  • 데이터가 n만큼 증가 할 때 Time Complexity는 n만큼 증가.
• O(log n)
  • 데이터가 n만큼 증가 할 때 Time Complexity는 n만큼 증가.

 

 

 

 

 

 

알고리즘 성능 평가시 고려 사항

• 최악의 경우
• 패턴
• 데이터수의 분포

 

 

 

 

 

 

 

 

알고리즘의 평가는 시간을 기준으로한 최악의 경우로 만들어진 패턴으로 평가한다.