160817(수) - 알고리즘 for Java [빅-오]

알고리즘 for Java [빅-오]

빅-오 표기법의 정의

O(g(n)) = {f(n) : n >= n0 인 모든 n에 대해 0 <= f(n) <= cg(n) 을 만족하는 양의 상수 c와 n0가 존재한다}

※ 목적은 "주어진 알고리즘의 증가율f(n)과 크거나 같은 최소의 증가율 g(n)을 찾는 것.

n이 작을 경우의 증가율은 중요하지 않으므로 생략(n0보다 작을 때의 증가율은 무시)

ex)

1. f(n) = 3n + 8의 상한은?

n >= 8인 모든 n에 대하여 3n + 8 = 4n

3n + 8 = O(n), c = 4, n0 = 8

2. f(n) = n^2 + 1의 상한은?

n >= 1인 모든 n에 대하여 n^2 + 1 <= 2n^2

n^2 + 1 = O(n), c = 1, n0 = 1

-> 이해 가지 않음. O(n^2), c = 2, n0 = 1 아닌가?

3. f(n) = n^4 + 100n^2 + 50의 상한은?

n >= 11인 모든 n에 대하여 n^4 + 100n^2 + 50 <= 2n^4

n^4 + 100n^2 + 50 = O(n^4), c = 2, n0 = 11

4. f(n) = 2n^3 - 2n^2의 상한은?

n >= 1인 모든 n에 대하여 2n^3 - 2n^2 <= 2n^3

2n^3 - 2n^2 = O(n^3), c = 2, n0 = 1

5. f(n) = n의 상한은?

n >= 1인 모든 n에 대하여 n <= n^2

n = O(n^2), c = 2, n0 = 1

-> c = 1 아닌가?

6. f(n) = 410의 상한은?

n >= 1인 모든 n에 대하여 410 <= 410

410 = n(1), c = 1, n0 = 1

※ 점근적 상한을 증명하는 유일한 n0와 c의 값은 없다.