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