반응형
- 성능분석
- 특정한 상황에서 더 효율적이고 성능이 뛰어난 알고리즘을 찾기 위해
- 정확성 : 정확하게 동작하는가?
- 작업량 : 얼마나 적은 연산을 수행하는가?
- 메모리 사용량 : 얼마나 적은 메모리를 사용하는가?
- 단순성 : 얼마나 단순한가?
- 최적성 : 더 이상 개선할 여지가 없을만큼 최적화되어 있는가?
- 수행 시간의 분석
- 컴퓨터의 성능과 관계없이 '작업량'을 활용하여 데이터의 크기의 변화에 대한 수행 시간을 예측
- 수행 시간 분석 방법
- 점근 표기법
- 마스터 정리
- NP-완전
- 수행 시간 분석을 통해 최악, 평균, 최적의 경우를 찾는 것이 목표
- 점근표기법
- 알고리즘 수행시간을 대략적으로 나타내는 방법
- Ο (Big O) 표기법 => 수행 시간의 상한
- Ω (Big Omega) 표기법 => 수행 시간의 하한
- Θ (Big Theta) 표기법 => 수행 시간의 상, 하한
- Ο 표기법
- O 를 쓰고 괄호 안에 증가 함수 => O (증가함수)
- 증가함수 -> 입력 데이터 n에 대한 수행 시간이 늘어나는 비율
- 최고차 항을 제외한 나머지 모든 항과 모든 계수를 제거
- Ex) 버블, 삽입 정렬의 증가 함수 : n^2/2 => 1/2 제거 => O(n^2)
반응형
