1. 알고리즘의 효율성/성능
※ 알고리즘 효율성은, 계산에 필요한 자원의 소요 량(量)이 적을수록 좋은 것 임
- 시간과 공간 측면에서 적게 소요되는 것이, 효율적이고 좋은 알고리즘 임
2. 알고리즘 효율성의 관점 구분
ㅇ 계산 시간 : 시간 복잡도 (Time Complexity)
- 주로, 수행 시간 관점에서, 알고리즘이 사용한 기본 연산의 수 (스텝 수,명령 수)
- 주요 기본 연산 : 정수의 비교,덧셈,곱셈,나눗셈 등
ㅇ 소요 메모리 : 공간 복잡도 (Space Complexity)
- 계산에 소요되는 컴퓨터 메모리
2. 알고리즘 효율성의 척도 : 계산 복잡도 (Computational Complexity, Complexity Metric)
ㅇ 주로, 시간 복잡도 위주로 따짐
ㅇ 다만, 최근의 빅데이터 처리에는 공간 복잡도도 점차 중요해 짐
3. 알고리즘 효율성의 분석 : 수행 시간 및 소요 메모리 분석
ㅇ 효율성 분석
- 알고리즘을 실행하는 데 필요한 시간,공간을 측정하는 것
ㅇ 분석 대상 : (입력) 크기, (분석대상) 소요 시간 및 공간
- 문제의 `입력 크기`가 증가함에 따라,
- `처리 시간(연산 수) 및 소요 메모리`가 얼마나 증가하는가를 분석함
* 입력 크기의 例)
. 배열의 크기, 다항식 차수, 행렬의 항목 수, 이진 입력 비트 수,
그래프에서 정점 및 가지 수 등
ㅇ 표현 방식 : 다항식 함수 형태
- 주로, `소요 공간` 보다는 `수행 시간`에 대해,
- 기본 연산 횟수를, 입력 크기 n에 따른 함수 f(n)을,
- 다항식 함수 형태로 표현
- 이는, 기계적인 속도나 프로그래밍 스타일과는 무관함
ㅇ 분석 방법 : 최악, 평균, 최선
- 최악 경우(worst-case), 평균 경우(average-case), 최선 경우(best-case) ☞ 시간 복잡도 참조
* 알고리즘 실행 시간을 정확히 측정하기 보다는,
. 입력 크기가 증가함에 따라, 소요 시간이 어떻게 변하는 지에 관심이 있음
ㅇ 표기법 : 점근적 표기법
- (최악의 경우) => big-O (빅 오 표기법) : O() => `최악, 이정도는 보장` (점근적 상한선)
- (최선의 경우) => big-Omega (빅 오메가 표기법) : Ω() => `최고 수준` (점근적 하한선)
- (평균의 경우) => big-Theta (빅 세타 표기법) : Θ() => `대략`