전제 조건 – 점근 표기법 , 점근 표기법의 속성 , 알고리즘 분석
1. 빅오 표기법(O):

이는 상한으로 정의되며 알고리즘의 상한은 필요한 최대 시간(최악의 경우 성능)입니다.
빅오 표기법 을 설명하는 데 사용됩니다. 점근 상한 .

수학적으로, 만약 에프(엔) 알고리즘의 실행 시간을 설명합니다. 에프(엔) ~이다 O(g(n)) 양의 상수가 존재하는 경우 씨 그리고 n0 그렇게,

0 <= f(n) = n0

N = 상한에 함수를 제공하는 데 사용됩니다.
함수가 다음과 같은 경우 에) , 자동으로 O(n-제곱) 또한.

다음에 대한 그래픽 예 빅오:

개인용 인스타그램의 장점

2. 빅 오메가 표기법(Ω) :

이는 하한으로 정의되며 알고리즘의 하한은 필요한 최소 시간입니다(가능한 가장 효율적인 방법, 즉 최상의 경우).
처럼 영형 표기법 제공하다 점근 상한 , 오 표기법 제공한다 점근 하한 .

허락하다 에프(엔) 알고리즘의 실행 시간을 정의합니다.
에프(엔) 이라고합니다 Ω(g(n)) 양의 상수가 존재하는 경우 씨 그리고 (n0) 그렇게

0 <= Cg(n) = n0

Java의 유형 캐스팅 및 유형 변환

N = 함수의 하한을 지정하는 데 사용됩니다.
함수가 다음과 같은 경우 Ω(n-제곱) 그것은 자동으로 아(n) 또한.

그래픽 예 빅오메가(Ω):

3. 빅 세타 표기법(Θ):

이는 가장 엄격한 경계로 정의되며 가장 엄격한 경계는 알고리즘이 취할 수 있는 모든 최악의 경우 시간 중 최고입니다.

허락하다 에프(엔) 알고리즘의 실행 시간을 정의합니다.
에프(엔) 이라고합니다 Θ(g(n)) 만약에 에프(엔) ~이다 O(g(n)) 그리고 에프(엔) ~이다 Ω(g(n)).

$와 $$의 차이

수학적으로,

0 <= f(n) = n0
0 <= C2g(n) = n0

두 방정식을 병합하면 다음과 같은 결과를 얻습니다.

0 <= C2g(n) <= f(n) = n0

방정식은 단순히 f(n)이 C2 g(n)과 C1g(n) 사이에 샌드위치되도록 양의 상수 C1과 C2가 존재한다는 것을 의미합니다.

그래픽 예 빅 세타(Θ) :

빅 오, 빅 오메가, 빅 세타의 차이점 :

자세한 내용은 다음을 참조하세요. 알고리즘 설계 및 분석 .