점근적 표기법
점근 표기법은 점근 분석을 위한 알고리즘의 복잡성을 나타내는 데 사용됩니다. 이러한 표기법은 복잡성을 나타내는 수학적 도구입니다. 일반적으로 사용되는 세 가지 표기법이 있습니다.
빅 오 표기법
Big-Oh(O) 표기법은 함수 f(n)의 상한을 상수 요소 내로 제공합니다.
f(n) =O(g(n)), n0의 오른쪽에 f(n)이 항상 c*g(n) 위 또는 아래에 있는 양의 상수n0 및 c가 있는 경우
O(g(n)) ={ f(n) :모든 n ≥ n0에 대해 0 ≤ f(n) ≤ c g(n)인 양의 상수 c와 n0이 존재함}
빅 오메가 표기법
Big-Omega(Ω) 표기법은 함수 f(n)의 하한을 상수 요소 내로 제공합니다.
f(n) =Ω(g(n))이라고 씁니다. 양의 상수n0과 c가 있고 n0의 오른쪽에 f(n)이 항상 c*g(n) 위에 있거나 위인 경우.
Ω(g(n)) ={ f(n) :모든 n ≥ n0에 대해 0 ≤ c g(n) ≤ f(n)인 양의 상수 c와 n0이 존재함}
큰 세타 표기법
Big-Theta(Θ) 표기법은 함수 f(n)에 대한 경계를 상수 요소 내로 지정합니다.
f(n) =Θ(g(n)), n0의 오른쪽에 f(n)이 항상 c1*g(n)과 c2*g 사이에 있도록 양의 상수 n0, c1 및 c2가 있는 경우 (n) 포함.
Θ(g(n)) ={f(n) :모든 n ≥ n0에 대해 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n)이 되도록 양의 상수 c1, c2 및 n0이 존재함}