점근(차츰 점, 가깔울 근) 표기법
=> 알고리즘의 수행시간을 대략적으로 나타내는 방법
ex)
데이터를 정렬하는데 필요한 작업 횟수 : (n^2 + 5n ) vs ( 27n )
=> 데이터의 크기가 커지면 커질수록 최고차 항을 제외한 나머지 항의 영향은 거의 없다
=> 때문에 점금 표기법에서는 알고리즘의 성능을 최고차 항으로만 '대략적으로' 표시한다
대표적인 점근 표기법 3가지
- O(Big O) 표기법
- Ω (Big Omega) 표기법
- Θ (Big Theta) 표기법
O(Big O) 표기법
- 최악의 경우 알고리즘 수행 시간
- 즉, 아무리 열악한 조건이라도 (입력이 아무리 크더라도) O 표기법으로 표현된 성능 수준에서 알고리즘이 종료된다는 의미
- 가장 많이 사용하는 알고리즘 성능 표기법
사용방법
- 대문자 O를 쓰고 그 옆에 괄호를 열고 닫은 후 그 안에 증가 함수를 넣는다
- 최고차 항을 제외한 나머지 모든 항과 모든 계수를 제거
ex)
2n^2 + 4n
=> n^2
=> O(n^2)
(1/2)n^2
=> n^2
=> O(n^2)
증가 함수
=> 입력 데이터의 크기 n에 대해 알고리즘의 수행 시간이 늘어나는 비율을 나타내는 함수
특이점 : O(n^3)
=> 점근적 상한 수행 시간이 n^3을 넘지 않는 모든 증가 함수의 '집합'
=> 위에 있는 알고리즘의 수행시간은 모두 점근적으로 n^3을 넘지 않기 때문에 O(n^3)으로 표현할 수 있다
Ω (Big Omega) 표기법
최선의 경우 알고리즘 수행 시간 (수행해야 하는 최소한의 수행 시간)
=> 아무리 좋은 조건을 만나도 꼭 수행해야만 하는 최소한의 수행시간
Θ (Big Theta) 표기법
'자료구조와 알고리즘 ft. 수업 > 알고리즘 성능 분석' 카테고리의 다른 글
1. 알고리즘 성능 측정 기준과 수행 시간 (0) | 2023.03.20 |
---|