성능분석
1. 어떤 알고리즘이 어떤 문제를 푸는가.
2. 어떤 알고리즘이 내가 처한 문제를 해결하는데 가장 효과적인가.
비용측면, 속도 측면
-특정 기계에서 수행시간을 측정하는 것은 공정하지 못하다.
장비에 따라 성능이 달라지기 때문에
따라서 조건이 동일한 특정기계에서 모든 알고리즘의 수행시간을 측정해야 하는데 이방법은
현실적으로 불가능합니다.
그러므로 수행연산의 횟수를 비교하는 방식으로 성능을 분석합니다.
ex)
안드로이드 10초 곱셈연산을 10번 했다고 생각할수 있음
pc 1초 0.1초 x 10번
서버 0.1초 0.01초 x10번
결국 알고리즘을 이용해 문제를 푼다는 것은 기본 함수가 있고 그 함수를 몇번 수행하는가를 구분 할 수 있다.
상대적인 비교!
수행시간은 입력으로 크기가 커지면 커질 수록 시간이 많이 걸린다.
10개의 키를 정렬하는 시간이 100개의 키를 정렬하는 시간보다 길다.
따라서 입력크기 n에 대한 함수로 표현한다.
예를 들면 t(n)
알고리즘 기본연산
1. 산술연산
+,*,-
2. 데이터 입출력
copy,move,save,load
3. 제어 연산
if,while,register
점근적 표기법
빅오 표기법
상한
오메가 표기법
하한
쎄타 표기법
상한과 하한을 모두 정의