[이산수학] 함수의 증가, big o notation

함수의 증가

함수 f(x)가 g(x)보다 더 빠르게 증가한다면, f(x)는 충분히 큰 x에 대해 항상 g(x)보다 커집니다.

 

사용자 데이터를 처리하는 웹 사이트를 설계한다고 가정해봅시다. 데이터 베이스 처리를 위해서 

 

프로그램 A는 n개 레코드를 처리하기 위해 fa(n) = 30n+8 microseconds가 걸립니다.

프로그램 B는 n개 레코드를 처리하기 위해 fa(n) = n^2+1 microseconds가 걸립니다.

 

Big - o notation

함수의 order에 대한 big o notation에 대해서 설명하겠습니다. f와 g를 정수의 집합 또는 실수의 집합에서 실수의 집합으로의 함수라고 하자. 만약 x > k 일 때, 다음을 만족하는 상수 c와 k가 존재한다면 f(x)는 o(g(X)) 라고 한다. 

 

|f(x)| <= C|g(x)| 

 

-직관적으로 f(x)가 O(g(x)) 라는 정의는 x가 커짐에 따라 f(x)는 g(x)의 고정된 배수보다 천천히 커진다는 것을 말합니다. 

 

f(x) is big-O of(g(x) or f는 기껏해야 g(x)의 차수라고 말합니다. 

 

상수 c와 k는 f(x)가 O(g(x)) 라는 관계에 대한 증인이라고 불립니다. 이 관계에 대한 한 쌍의 증인이 필요합니다.