[알고리즘] 차수

복잡도 함수 : 입력값의 크기에 따라 시행 횟수를 추측하는 함수.

0보다 큰 정수를 가짐.

 

Linear Time 알고리즘 : n이 인풋일 때 1차식으로 복잡도 함수가 나오는 알고리즘

Quadratic Time 알고리즘 : 2차식으로 복잡도 함수가 나오는 알고리즘

 

Order(차수)

어떤 알고리즘의 복잡도 함수의 최고차항의 차수

입력값이 커질 수록 차수는 알고리즘의 복잡도에 큰 영향을 미친다.

각 차수 별 입력값 증가에 따른 복잡도 증가

세타(Theta)의 집합은 빅오와 오메가의 교집합이다.

 

빅오

f(n)이라는 복잡도 함수의 빅오는

f(n)*양의 상수c를 했을 떄 무조건 작거나 같은 g(n)

 

다시 말해

어떤 N을 기준으로 cf(n)이 g(n)보다 무조건 크거나 같은 경우, g(n)은 f(n)의 빅오에 포함된다.

차수가 같거나 작은 g(n)의 경우 f(n)의 빅오에 포함된다.

 

오메가

빅오와 비슷하지만 g(n)이 cf(n)보다 크거나 같은 g(n).

차수가 크거나 같은 g(n)의 경우, 오메가에 포함된다.

스몰오

차수가 낮은 것의 집합.

모든 양수 c에 대해서 f(n)보다 g(n)이 작다.

 

정리

여기서 n!은 다른 복잡도 함수보다 훨씬 더 비효율적(값이 커짐)이다.

 

극한을 이용한 두 복잡도 함수의 차수 관계

로피탈의 정리

만약 f(x)와 g(x)가 미분 가능할 때...