4. 차수 표기법 및 차수에 대한 정의

차수 표기법 및 차수에 대한 정의

 - Big O   ( O )

 - Omega ( Ω )

 - Theta   ( Θ )

 - Small o ( o )

1. Theta ( Θ )

  N 이상의 모든 정수 n에 대해서 다음 부등식이 만족하는 양의 실수 c, d와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

 주어진 복잡도 함수 f(n)에 대해서 다음과 같이 정의한다.

2. Big O ( O )

  주어진 복잡도 함수 f(n)에 대해서 O(f(n))은 정수 N 이상의 모든 n에 대해서 다음 부등식이 성립하는 양의 실수 c와 음이 아닌 정수 N이 존재 하는 복잡도 함수 g(n)의 집합이다.

3. Omega ( Ω )

  주어진 복잡도 함수 f(n)에 대해서 은 N 이상의 모든 n에 대해서 다음 부등식을 만족하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

4. Small o ( o )

  주어진 복잡도 함수 f(n)에 대해서 o(f(n))은 모든 양의 실수 c에 대해서 을 만족하는 모든 n에 대해서 다음 부등식을 만족하는 음이 아닌 정수 N이 존재하는 모든 복잡도 함수 g(n)의 집합이다.

(아직 다 올린거 x )