알고리즘의 성능 분석

복잡도 분석

알고리즘의 복잡도 분석은 구현하지 않고도 모든 입력을 고려하는 방법이고 실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다.
복잡도 분석에는 실행 시간을 분석하는 시간 복잡도(time complexity)와
알고리즘이 사용하는 기억 공간을 분석하는 공간 복잡도(space complexity)가 존재하는데, 알고리즘의 복잡도를 이야기할 때 대게는 시간 복잡도를 말한다.(알고리즘이 차지하는 공간보다는 실행시간에 더 관심이 많기 때문!)

시간복잡도

알고리즘이 이루고 있는 연산들이 몇번이나 실행되는지를 숫자로 표시한다.(연산에는 산술, 대입, 비교, 이동 연산등이 있다.) 아래그림은 이러한 연산실행 횟수를 n이라고 할 때의 시간 복잡도를 빅오 표기법으로 나타낸것이다.(이 때, 알고리즘의 효율성은 대개 최악의 경우(worst case)을 시간 복잡도의 척도로 많이 쓰인다.)