알고리즘 성능 분석

알고리즘을 평가하는 데 있어 수행 시간과 메모리 사용량을 평가기준으로 두는데,
수행 시간에 해당되는 것이 시간 복잡도, 메모리 사용량에 해당되는 것이 공간 복잡도이다.

보통 알고리즘의 성능 분석은 복잡도를 계산하여 점근적 표기법으로 나타낸다.

 

점근적 분석

입력 값의 개수에 따라 알고리즘의 수행 시간을 바탕으로 알고리즘의 효율성을 평가한다.

 

점근적 표기

 

1) 빅오 표기법 O

• 점근적 상한선으로 점근적 증가율이 f(N)을 넘지 않는 모든 함수들의 집합이다.
• 즉, 최고 차항의 차수가 f(N)과 같거나 더 작은 함수들의 집합이다.
• f(N) <= c*g(N)
• 입력의 크기 N에 대해 O(N²) 일 경우, 기껏해야 N²에 비례하는 시간이 소모된다.

 

2) 오메가 표기법 Ω

• 점근적 하한선으로 점근적 증가율이 적어도 f(N)이 되는 모든 함수들의 집합이다.
• c*g(N) <= f(N)
• 입력의 크기 N에 대해 Ω(N²) 일 경우, 적어도 N²에 비례하는 시간이 소모된다.

 

3) 세타 표기법 Θ

• 점근적 상한선과 하한선의 교집합으로 아무리 좋아지거나 나빠지더라도 범위 안에 있다.
• c1*g(N) <= f(N) <= c2*g(N)
• 입력의 크기 N에 대해 Θ(N²) 일 경우, 대략 N²에 비례하는 시간이 소모된다.