점근적 표기법(asymptotic notation)
- big-Theta 표기법
- big-O 표기법
- big-Omega 표기법
알고리즘의 실행시간을 파악하는 방법 두가지
-
입력값의 크기에 대한 함수로 찾기
배열의 크기가 커지면 선형 검색과 이진 검색의 최대 추측 횟수가 함께 증가하기 때문
-
성장률(입력값의 크기에 따라 함수가 얼마나 빨리 커지는지) 알아보기
y = ax^2 + bx + c와 같은 그래프에서 중요하지 않은 항과 상수를(a, bx, c 같은 것) 제거하고 이해에 불필요한 부분을 배제하고 생각하면, 알고리즘의 실행시간에 중요한 부분인 성장률에 집중할 수 있다.
이렇게 상수 계수와 중요하지 않은 항목을 제거한 것이 점근적 표기법이다.
빅세타 표기법
최악의 경우를 생각해보면, 루프를 돌 때 걸리는 선형검색 시간은 다음과 같다.
(for문을 한 번 도는데 걸리는 시간 * n번의 루프횟수) + (for문을 만드는 데 걸리는 추가적인 시간)
여기서 중요한 것은 배열의 크기인 n이다. n이 실행시간에 가장 큰 영향을 주고, 이를 빅세타라고 부른다.
- 빅세타 표기법은 시간 단위를 고려할 필요가 없다는 이점이 있다.
- 보통 상수 인자와 낮은 차원의 항목은 생략하고 사용한다.
- 빅세타 표기법을 사용하는 이유 : 실행시간에 점근적으로 근접한 한계값이 있음을 표현하기 위해서.
- 점근적으로 : 큰 값의 n에 대해서만 적용되기 때문
- 근접한 한계값 : 위아래로 상수값 내에서 실행시간을 좁힐 수 있다는 뜻
알고리즘을 분석할 때 보게 되는 함수를 점근적 표기법으로 표기한 뒤, 커지는 속도가 느린 것부터 나열한 것.
- 빅세타 표기법의 한계 : 실행시간에 대해서 위아래에 점근적으로 근접한 한계. 예를 들어 이진 검색이 모든 경우에 세타(logn)이라고 할 수 없다. 왜냐하면 첫번째 추측에 찾으면 세타(1)이기 때문. 이진 검색의 실행시간은 절대 세타(logn)이상이지 않지만 더 좋을 때도 있다.
Big-O 표기법
빅세타 표기의 한계를 보완하기 위해, 빅오 표기법은 “실행 시간은 최대한 이만큼 커지지만 더 천천히 커질 수도 있다”는 의미로 사용.
-
이진 검색의 실행시간은 항상 O(logn)이다. 최악의 경우에는 세타(logn)이고, 모든 경우를 포괄하는 일반적 표현은 O(logn)이다.
-
다시말해, 최악의 경우를 뜻하는 세타(logn)과 일반적인 시간을 나타내는 O(logn)은 최악의 실행시간이 걸릴 때 동일하다. 그러나 이진검색이 항상 O(logn)시간 안에 실행되지만, 항상 세타(logn)시간에 실행된다고는 할 수 없다.
-
big-O 표기법은 점근적 상한선만 제공하고 점근적으로 근접한 한계를 주지 않는다. 그 예시는 아래와 같다.
10달러를 가지고 있는데, 친구에게 가서 “내 지갑에 들은 돈은 확실히 100만 달러보다는 적게 있어”라고 말한다면 정확하다고 할 수 없지만 명백한 사실이다.
big-omega 표기법
점근선 하한선을 표현해, 알고리즘이 상한선 없이 최소한 어느정도 걸린다고 말하고 싶을 때 사용한다.
- 세타(f(n))이 자동적으로 O(f(n))을 의미하는 것처럼, 자동적으로 오메가(f(n))을 의미한다. 이진 검색 실행 시간의 최악의 경우는 오메가(logn)이라고 할 수 있다. 이진검색에서 최소한의 시간은 오메가(1)이다. 적어도 상수 시간 이상이 걸리는 것을 알기 때문이다.
