알고리즘4. 점근적 증가율에 따른 함수 분류

1. Analyzing Algorithms and Problems: Principles and Examples

 

1-3. Classifying Functions by Their Asymptotic Growth Rates 점근적 증가율에 따른 함수 분류

 

Clasifying Functions

asymptotic growth rate점근적 증가율, asymptotic order점근적 순서 또는 order of functions함수 순서

• asymptotic: input size n이 충분히 커짐을 뜻함
• n이 충분히 커졌을 때 함수의 증가율
• 상수 인자와 small input을 무시하는 함수 비교 및 분류.

 

The Sets big oh O(g), big thetaθ(g), big omega Ω(g)

f와 g가 음이 아닌 정수에서 음이 아닌 실수까지의 함수라고 하자.

실수 상수 c > 0 이고 음이 아닌 정수 상수는 n0라고 했을 때 다음 두 상수에 대하여

 

O(g)

• 모든 n ≥ n0 에 대하여, f(n) ≤ c g(n) 인 함수 f의 집합
• upper bound
• g의 증가율보다 작거나 같다

 

big omega Ω(g)

• 모든 n ≥ n0 에 대하여, f(n) ≥ c g(n) 인 함수 f의 집합
• lower bound
• g의 증가율보다 크거나 같다

 

big theta θ(g)

• O(g) ∩ Ω(g)
• 두 함수의 교집합
• f, g 증가율 동일

 

f ∈ θ(g) read as 

“f is asymptotic order g” or “f is order g”

 

 

Comparing Asymptotic Growth Rates 점근적 증가율 비교

f(n) : 분석한 알고리즘의 복잡도

g(n) : 기준이 되는 함수

n이 무한하게 커질 때 f(n)과 g(n)을 비교하면 f가 g에 관해 어떤 notation에 포함되는지 알 수 있다. 

 

 

Asymptotic Growth Rates

 

input size n에 따라 필요한 Basic Operation 수를 나타내는 표

• n의 크기가 커질 수록 필요한 연산 수는 크게 증가한다.
• 연산 시 시간이 많이 걸리는 2의 n제곱 함수는 암호설계 시에 사용된다.

Runtime = 필요 연산 수 = 수행 시간

• n이 충분히 커졌을 때, 1차식 함수가 2차식 함수보다 효율이 좋다.
• input size n < 25일 때 A는 B보다 더 빠른 시간 내에 문제를 해결한다.
• input size n = 25일 때 A가 B함수의 증가율을 앞지른다.
• 즉, 입력 크기가 25 아래일 때는 A 알고리즘을, 25 위일 때는 B 알고리즘을 사용하는 것이 효율적이다.

 

Properties of O(g), θ(g), Ω(g) 이런 게 있구나 정도만 공부. 강의노트에서 앞으로 안 나옴.

Transitive

• 이행성
• 논리학의 삼단논법과 비슷한 구조
• If f ∈ O(g) and g ∈ O(h), then f ∈ O(h) ☞ O is transitive.
• Ω, θ, o, ω도 transitive 만족

Reflexive

반사성

• f ∈ θ(f)
• 동일 함수 f끼리 자리 바꿔도 만족
• O, Ω도 Reflexive 만족

Symmetric

• 대칭성
• If f ∈ θ(g), then g ∈ θ(f)
• 두 개 함수 다를 때(f, g) 위치 바꿔도 만족
• 대칭성은 빅세타만 만족

θ defines an equivalence relation(동치 관계) on the functions. ☞ 빅세타만 유일하게 위의 세 가지 특성을 다 만족.

 

Each set θ(f) is an equivalence class (complexity class). ☞ 동치관계이므로, 같은 증가율을 갖는 함수들의 class를 모두 가지고 있다. 

 

f ∈ O(g) ⇔ g ∈ θ(f)

• 필요충분 조건(if and only if)
• 함수 자리 바꾸면 노테이션도 바뀜.

 

O(f + g) = O(max(f, g)) 

• 두 함수의 sum은 두 함수의 max, 즉 최고차항만 보면 됨

ex.

f = 3n² + 7n + 100

g = 5n³ + 3

O(f + g) = O(n³) ▷최고차항만 따지면 된다.

• Ω, θ 둘 다 max로 정의 가능(min 아님!)

 

Example: Classification of Functions

• O(1) = O(c) = O(0) : 상수시간. input size n에 관계없이 항상 일정한 수행시간
• f ∈ θ(n), f is linear(1차식); f ∈ θ(n²), f is quadratic(2차식); f ∈ θ(n³), f is cubic(3차식)

• lg n의 증가율이 다항함수보다 작다.
• 이때 α > 0이며, 분수를 포함한다. 즉, α = 1/2일 때 n의 α제곱은 √n이며 이때도 lg n이 기울기가 더 작다.

• for any k > 0 and any c > 1
• k가 양수이므로 n^k는 다항식.
• c > 1이므로 c^n은 지수함수. n이 커지면 c^n 값도 커진다. ↔ if c < 1, n이 커지면 c^n은 점점 0에 수렴한다.
• n이 점점 커지면 n^k는 임의의 지수함수 c^n보다 작음(천천히 증가. 즉, 증가율이 작음)

*n! 의 증가율 기억해두기★★★

stirling's approximation

1. n! ∈ o(nⁿ) ☞ nⁿ보다 n!의 증가율이 더 작다.

2. n! ∈ ω(2ⁿ) ☞ 2ⁿ보다 n!의 증가율이 더 크다.

3. log(n!) ∈ θ(log nⁿ) ☞ 1번에 양변 로그→ 증가율 같아짐

             ∈ θ(nlog n)

 

 

 

 

---

자료 출처

Computer Algorithms

(Sara Baase, Allen Van Gelder저, Addison Wesley, 2000)