Complexity function 및 빅 오 , 빅 오메가, 빅 세타 표기법

Complexity function 및 빅 오 , 빅 오메가, 빅 세타 표기법

알고리즘 분석에 필요한 두 개의 Parameter 

 

the input size

the basic operation

 

Input Size 

 

1. array의 size가 Input size가 될 수 있습니다.

 

2. single number자체가 input size가 될 수 있습니다.

 

3. 그래프가 입력으로 들어온다면, vertex의 개수, edge의 개수가 input size가 될 수 있습니다.

 

 

 

Basic Operation

 

알고리즘 전체의 수행 시간에 미미하게 영향을 끼치는 것을 제외하고

전체의 수행 시간을 지배하게 되는 그룹을 Basic Operation이라고 합니다.

Example) Binary Search에서는 찾고자 하는 값과 중간 값을 비교하는 연산이 Basic Operation입니다.

 

 

 

Time Complexity

각각의 Input size에 대해서 Basic Opeation이 몇 번 실행되었느냐를 결정하는 것.

 

 

 

Complexity Function

주어진 입력에 대해서 알고리즘의 Basic operation이 몇 번 수행되었는가를 나타내는 함수

 

알고리즘의 complexity function이 주어지면 그것의 최고차항이 그 알고리즘의 속도를 지배하게 됩니다.

 

 

 

Big O 표기법

 

complexity function f(n)의 O (f(n)) 는

g(n) ≤ c x f(n) (c는 음이 아닌 특정 상수)을 만족하는 

complexity function g(n)의 집합입니다.

 

complexity function g(n)이 complexity function f(n)에 대해

g(n) ≤ c x f(n)을 만족한다면

'g(n)은 f(n)의 Big O이다'라고 정의할 수 있고

g(n) ∈ O (f(n))이라고 표기할 수 있는 것입니다.

 

 

 

Big Omega 표기법

 

complexity function f(n)의 Ω (f(n)) 는

g(n) ≥ c x f(n) (c는 음이 아닌 특정 상수)을 만족하는 

complexity function g(n)의 집합입니다.

 

complexity function g(n)이 complexity function f(n)에 대해

g(n) ≥ c x f(n)을 만족한다면

'g(n)은 f(n)의 Ω이다'라고 정의할 수 있고

g(n) ∈ Ω (f(n))이라고 표기할 수 있는 것입니다.

 

쉽게 생각하면 Big O 표기법의 반대이죠.

 

 

 

Big Theta 표기법

 

complexity function f(n)의 θ (f(n)) 는

위에서 살펴본 Ω 와 O를 모두 만족하는 경우입니다. 

 

즉 c x f(n) ≤ g(n) ≤d x f(n) (c,d는 음이 아닌 특정 상수)를 만족하는

complexity function g(n)의 집합입니다.

 

complexity function g(n)이 complexity function f(n)에 대해

c x f(n) ≤ g(n) ≤ d x f(n)를 만족한다면

'g(n)은 f(n)의 θ이다'라고 정의할 수 있고

g(n) ∈  θ(f(n))이라고 표기할 수 있는 것입니다.