알고리즘의 성능 분석

알고리즘 성능 분석 기준

---

알고리즘 성능을 분석하는 판단 기준에는 정확성, 명확성, 수행량, 메모리 사용량, 최적성 등이 있음.

• 정확성
  • 올바른 자료가 입력되었을 때 유한한 시간 내에 올바른 결과를 출력할수 있는지
• 명확성
  • 알고리즘이 얼마나 이해하기 쉽고 명확하게 작성되었는지
• 수행량
  • 기본적으로 포함되는 연산 제외, 알고리즘의 특성을 나타내는 중요 연산을 모두 분석
• 최적성
  • 가장 중요, 알고리즘을 적용할 시스템의 사용 환경과 중요 요구사항이 모두 다르기 때문에 ‘가장 좋은’ 알고리즘이란 조건에 맞는 ‘최적의’ 알고리즘이라 할 수 있음.

---

알고리즘 성능 분석 방법

---

• 공간 복잡도 (Space Complexity)
  • 알고리즘을 프로그램으로 실행하여 완료하는 데까지 필요한 총 저장 공간
  • 필요한 고정 공간 + 가변 공간

• 시간 복잡도 (Time Complexity)
  • 컴파일 시간은 제외, 명령문의 실행 빈도수를 계산하여 측정.
  • 시간 복잡도는 각 알고리즘을 서로 비교하기 위한 것으로 실행 빈도수를 구하여 사용.

---

알고리즘 성능 분석 표기법

1. Big-Oh (빅-오)

---

빅-오 표기법은 함수의 상한을 나타내기 위한 표기법.

최악의 경우에도 g(n)의 수행 시간 안에는 알고리즘 수행이 완료된다는 것을 보장함.

2. Big-Omega (빅-오메가)

---

빅-오메가는 함수의 하한을 나타내기 위한 표기법.

알고리즘 수행에는 적어도 g(n)의 수행 시간이 필요함을 의미함.

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

3. Big-Theta (빅-세타)

---

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

즉, f(n)=heta(g(n)) 이려면 f(n)=O(g(n)) 이면서 f(n)=Omega(g(n)) 이어야 함.

시간 복잡도를 정확히 계산할 수 있다면 빅-세타 표기법 사용.

---