Big-Ω (빅 오메가) 표기법
ko.khanacademy.org
*이 글은 위 링크의 내용을 필사하거나 요약한 글입니다.
빅 오메가 표기법이란
가끔은 알고리즘을 표현할때 최소한 어느 정도 걸린다고 말할 때가 있을겁니다. 이럴 때 사용하는 표기법이 빅 오메가 표기법입니다.
실행시간이 Ω(f(n))라면 n이 충분히 클 때 실행 시간은 어떤 상수 k에 대해 최소 k*f(n)입니다. 아래의 그래프를 보면 이해할수있습니다.
빅오메가 표기법은 점근적 하한선을 표현하기 위해 사용합니다. 점근적 하한선은 충분히 큰 입력에서 실행 시간을 밑에서 제한하기 때문입니다.
Θ(f(n))이 O(f(n)의 의미를 포함했던 것처럼 자동적으로 Ω(f(n))의 의미도 포함합니다. 따라서 이진 검색 실행 시간의 최악의경우는 Ω(log2n)라고 할 수 있습니다.
이상입니다.