입력자료의 개수가 큰 경우에는 차수가 가장 큰 항이 전체의 값을 주도하기 때문에 보통 시간복잡도 함수에서 차수가 가장 큰 항만을 고려하면 충분함.
+ 수행시간이 서로 다른 연산들의 수행 시간을 같다고 가정하였기 때문에 정확한 비교가 의미가 없을 수도 있음.
따라서 시간 복잡도 함수에서 중요한 것은 n이 증가하였을 때 연산의 총 횟수가 n에 비례하여 증가하는지, 아니면 다른 증가추세를 가지는지가 더 중요함.
'시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복 잡도를 표시하는 방법'을 빅오 표기법이라고 함.
즉 알고리즘이 n에 비례하는 수행시간을 가진다고 말하는 대신에 알고리즘 의 시간복잡도가 O(η) 이라고 함.
빅오 표기법의 수학적 정의
두개의 함수 f(n)과 g(n)이 주어졌을 때,
모든 n≥n0에 대하여 |f(n)| ≤ c|g(n)|을 만족하는 2개의 상수 c와 n0가 존재하면 f(n)=O(g(n))이다.
빅오는 함수의 상한을 표시한다.
(예) n≥5 이면 2n+1 <10n 이므로 2n+1 = O(n)
빅오 표기법을 얻는 간단한 방법은 기본연산의 횟수가 다항식으로 표현되었을 경우 다항식의 최고차항만을 남기고 다른 항들과 상수항을 버리는 것. (최고차항의 계수도 버리고 최고차항만의 차수만을 사용)
😎빅오표기법 외의 표기법
빅오메가와 빅쎄타 표기법이 있지만 간단히만 설명하면, 빅오 표기법은 상한을 표기한 것이므로 상한은 여러 개가 존재할 수 있다. 그러나 빅오 표기법이 최소 차수 함수로 표기되었을 경우만 의미가 있기 때문에 이와 같은 문제점을 보완하기 위해 빅오메가와 빅쎄타 표기법이 있다.
빅오메가 : 함수의 하한을 표시
빅세타 : 동일한 함수로 상한과 하한을 만들 수 있는 경우
🙄최선, 평균, 최악
알고리즘의 수행시간은 입력 자료 집합에 따라 다를 수 있음.
알고리즘의 효율성은 주어지는 자료집합에 따라 다음의 3가지로 나누어서 평가할 수 있음.
- 최선의 경우 : 수행 시간이 가장 빠른 경우
- 평균의 경우 : 수행 시간이 평균적인 경우
- 최악의 경우 : 수행 시간이 가장 늦은 경우
서로간의 뭐가 좋고 나쁘고라기보단, 각각의 경우가 다르다. 순차탐색을 예로 들면,
| 최선의 경우 | 찾고자 하는 숫자가 맨 앞에 있는 경우 |
| 최악의 경우 | 찾고자 하는 숫자가 맨 뒤에 있는 경우 |
| 평균적인 경우 | 찾고자 하는 숫자가 중간쯤에 있는 경우 |
결론은,
- 최선의 경우 : 의미가 없는 경우가 많다.
- 평균적인 경우 : 계산하기가 상당히 어려움.
- 최악의 경우 : 가장 널리 사용된다. 계산하기 쉽고 응용에 따라서 중요한 의미를 가질 수도 있다.
(예) 비행기 관제업무, 게임, 로보틱스