algorithm
알고리즘 복잡성

비고

total = 0
for(i = 1; i < 10; i++)
    total = total + i

빅 쎄타 표기법

Big-O 표기법은 일부 알고리즘의 실행 시간 상한을 나타 내기 때문에 단단한 경계입니다. 상한과 하한 둘 다. 엄격한 경계는 더 정확하지만 계산하기가 더 어렵습니다.

Big-Theta 표기법은 대칭입니다 : f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))

그것을 이해하는 직관적 인 방법은 f(x) = Ө(g(x)) 는 f (x)와 g (x)의 그래프가 동일한 비율로 증가하거나 그래프가 ' x의 충분한 값.

Big-Theta 표기법의 전체 수학 식은 다음과 같습니다.
모든 n> n에 대해 c ₁ <abs (g (n) / f (n)) 인 경우, f (x) = {g : N ₀ → R 및 c ₁ , c ₂ , n ₀ > ₀ 이고 abs는 절대 값입니다.}

예제

입력 n 대한 알고리즘이 42n^2 + 25n + 4 연산을 완료하는 데 O(n^2) 이지만 O(n^3) 및 O(n^100) 라고도합니다. 그러나 Ө(n^2) 이고 Ө(n^3) , Ө(n^4) 등이 아닙니다. Ө(f(n)) 알고리즘 또한 O(f(n)) 그 반대도 마찬가지입니다!

공식적인 수학적 정의

Ө(g(x)) 는 함수 집합입니다.

Ө(g(x)) = {f(x) such that there exist positive constants c1, c2, N such that 0 <= c1*g(x) <= f(x) <= c2*g(x) for all x > N}

때문에 Ө(g(x)) 세트는, 우리가 쓸 수 f(x) ∈ Ө(g(x)) 을 나타 내기 위해 f(x) 의 멤버 Ө(g(x)) . 대신 우리는 보통 f(x) = Ө(g(x)) 를 써서 동일한 개념을 표현합니다. 이는 일반적인 방법입니다.

수식에 Ө(g(x)) 가 나타날 때마다 우리는 이름을 붙이지 않는 익명의 기능을 나타내는 것으로 해석합니다. 일례 방정식 T(n) = T(n/2) + Ө(n) , 수단 T(n) = T(n/2) + f(n) f(n) 의 설정의 함수이다 Ө(n) .

f 와 g 실수의 일부 서브 세트에서 정의 된 두 개의 함수라고하자. 포지티브 상수 K 와 L 과 실체 x0 가있는 경우에만 f(x) = Ө(g(x)) 를 x->infinity 로 씁니다.

K|g(x)| <= f(x) <= L|g(x)| 모든 x >= x0 .

정의는 다음과 같습니다.

f(x) = O(g(x)) and f(x) = Ω(g(x))

한계를 사용하는 방법

limit(x->infinity) f(x)/g(x) = c ∈ (0,∞) 때 한계가 존재하고 양수이면 f(x) = Ө(g(x))

공통적 인 복잡성 클래스

빅 오메가 표기법

Ω- 표기법은 점근 적 하한에 사용됩니다.

형식 정의

f(n) 과 g(n) 양의 실수의 집합에 정의 된 두 개의 함수라고하자. 다음과 같이 양의 상수 c 와 n0 가있는 경우 f(n) = Ω(g(n)) 이라고 씁니다.

0 ≤ cg(n) ≤ f(n) for all n ≥ n0 .

노트

f(n) = Ω(g(n)) 은 f(n) 이 점차적으로 g(n) 보다 느리게 성장하지 않음을 의미합니다. 또한 알고리즘 분석이 Θ(g(n)) 또는 / 및 O(g(n)) 대한 설명으로 충분하지 않을 때 Ω(g(n)) 에 대해 말할 수 있습니다.

표기법의 정의로부터 다음과 같은 정리가 나온다.

두 가지 모든 기능을 위해 f(n) 와 g(n) 우리가 f(n) = Ө(g(n)) 경우에만, f(n) = O(g(n)) and f(n) = Ω(g(n)) 이다.

그래픽으로 Ω 표기법은 다음과 같이 나타낼 수있다.

예를 들어 f(n) = 3n^2 + 5n - 4 가질 수 있습니다. 그러면 f(n) = Ω(n^2) . 그것은 또한 올바른 f(n) = Ω(n) 또는 심지어 f(n) = Ω(1) 입니다.

완벽한 매칭 알고리즘을 해결하는 또 다른 예제 : 정점 수가 홀수이면 "No Perfect Matching"을 출력하고 그렇지 않으면 가능한 모든 매치를 시도하십시오.

우리는 알고리즘이 기하 급수적으로 시간을 필요로하지만, 사실은 당신이 증명할 수없는 말을하고 싶은 Ω(n^2) 의 일반적인 정의를 사용하여 하한 Ω 알고리즘이 홀수 n 개의 선형 시간에 실행하기 때문이다. 무한히 많은 n 대해 어떤 상수 c>0 , f(n)≥ cg(n) 대해 말함으로써 f(n)=Ω(g(n)) 을 정의해야합니다. f(n)=Ω(g(n)) iff f(n) != o(g(n)) .

참고 문헌

정식 정의와 정리는 "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms"책에서 가져온 것입니다.

점근 표기법의 비교

f(n) 과 g(n) 양의 실수의 집합에 정의 된 두 개의 함수 라하자. c, c1, c2, n0 는 양의 실수 상수이다.

표기법	f (n) = O (g (n))	f (n) = Ω (g (n))	f (n) = Θ (g (n))	f (n) = o (g (n))	f (n) = ω (g (n))
형식 정의	∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) ≤ cg(n)	∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) ≤ f(n)	∃ c1, c2 > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n)	∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) < cg(n)	∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) < f(n)
f, g 와 실수 a, b 의 점근 비교	a ≤ b	a ≥ b	a = b	a < b	a > b
예	7n + 10 = O(n^2 + n - 9)	n^3 - 34 = Ω(10n^2 - 7n + 1)	1/2 n^2 - 7n = Θ(n^2)	5n^2 = o(n^3)	7n^2 = ω(n)
그래픽 해석

점근 표기법은 다음과 같이 벤 다이어그램에서 나타낼 수 있습니다.

모래밭

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. 알고리즘 소개.