Big Omega(Ω) 및 Big Thera(θ) 표기법

점근적 표기법

점근 표기법은 점근 분석을 위한 알고리즘의 복잡성을 나타내는 데 사용됩니다. 이러한 표기법은 복잡성을 나타내는 수학적 도구입니다. 일반적으로 사용되는 세 가지 표기법이 있습니다.

빅 오메가 표기법

Big-Omega(Ω) 표기법은 함수 f(n)의 하한을 상수 요소 내로 제공합니다.

f(n) =Ω(g(n)), n₀ 오른쪽에 다음과 같은 양의 상수 n0 및 c가 있는 경우 f(n)은 항상 c*g(n) 또는 그 위에 있습니다.

Ω(g(n)) ={ f(n) :모든 n ≤ n₀에 대해 0 ≤ c g(n) ≤ f(n)인 양의 상수 c와 n0이 존재합니다. }

큰 세타 표기법

Big-Theta(Θ) 표기법은 함수 f(n)에 대한 경계를 상수 요소 내로 지정합니다.

우리는 f(n) =Θ(g(n))이라고 씁니다. 양의 상수 n0과 c₁이 있는 경우 및 c₂ n₀ 오른쪽으로 f(n)은 항상 c₁ 사이에 있습니다. *g(n) 및 c₂ *g(n) 포함.

Θ(g(n)) ={f(n) :양의 상수 c₁가 존재 , c₂ 및 n₀ 0 ≤ c₁ g(n) ≤ f(n) ≤ c₂ g(n), 모든 n ≥ n₀에 대해 }