Big-Ω (빅 오메가) 표기법

때로는 알고리즘이 상한선 없이 최소한 어느 정도 걸린다고 해야 할 때도 있을 것입니다. 그럴 때는 big-Ω 표기법을 사용합니다. 여기서 Ω는 그리스 문자 "오메가"입니다.

실행 시간이

Ω (f (n))

라면

n

이 충분히 클 때 실행 시간은 어떤 상수

k

에 대해 최소

k \cdot f (n)

입니다. 실행 시간이

Ω (f (n))

인 경우는 다음과 같이 생각할 수 있습니다.

여기서 실행 시간은 "

f (n)

의 big-Ω"라고 합니다. 점근적 하한선을 표현하기 위해선 big-Ω 표기법을 사용하는데, 그 이유는 점근적 하한선은 충분히 큰 입력 크기에서 실행 시간을 밑에서 제한하기 때문입니다.

Θ (f (n))

이 자동적으로

O (f (n))

을 의미하는 것처럼, 자동적으로

Ω (f (n))

도 의미합니다. 따라서 이진 검색 실행 시간 최악의 경우는

Ω (\log_{2} n)

이라고 할 수 있습니다.

맞긴 하지만 정확하지는 않은 big-Ω 표기법의 예를 들면, 주머니에 백만 달러가 있을 때, 주머니에 돈이 있긴 한데 적어도 10 달러는 된다고 말하는 것이 진실인 것처럼 이진 검색은 최소한 상수의 시간이 걸리므로 이진 검색 최악의 경우 실행 시간은

Ω (1)

라고 말할 수 있습니다. 적어도 상수 시간 이상이 걸리는 것을 알기 때문입니다.

당연히 알고리즘을 다룰 때에는 가장 정확한 방법을 사용하는 것이 좋습니다. 여기서 위와 같은 예를 든 이유는 big-

Ω

, big-

O

, big-

Θ

의 이해를 돕기 위한 것뿐입니다.

대화에 참여하고 싶으신가요?

정렬 기준:

포스트가 아직 없습니다.