big O 표기법과 유사하게 big Omega (Ω) 함수는 알고리즘의 성능 또는 복잡성을 설명하기 위해 컴퓨터 과학에서 사용됩니다.
실행 시간이 Ω (f (n))이면 n이 충분히 클 경우 실행 시간은 일부 상수 k에 대해 최소한 k⋅f (n)입니다. Ω (f (n)) 인 실행 시간을 생각하는 방법은 다음과 같습니다.
실행 시간은 "f (n)의 큰 Ω"이라고 말합니다. 충분히 큰 입력 크기에 대해 아래에서 실행 시간의 증가를 제한하기 때문에 점근 하한에 대해 big-Ω 표기법을 사용 합니다.
Big O와 Big Ω의 차이
Big O 표기법과 Big Ω 표기법의 차이점은 Big O가 알고리즘의 최악의 실행 시간을 설명하는 데 사용된다는 것입니다. 그러나 Big Ω 표기법은 주어진 알고리즘에 대한 최상의 실행 시간을 설명하는 데 사용됩니다.
추가 정보:
- Big-Ω (Big-Omega) 표기법
