이 기능의 성장 순서를 찾는 데있어 적절한 방법은 무엇입니까?

Question

2^n + 6n^2 + 3n

나는 그것이 가장 높은 순서 용어를 사용하는 O (2^n) 일 뿐이라고 생각하지만, 이것을 증명하는 공식적인 접근법은 무엇입니까?

Answer 1

당신은 그것을 증명할 수 있습니다 2^n + n^2 + n = O(2^n) 인피니티에서 한계를 사용하여. 구체적으로, f(n) ~이다 O(g(n)) 만약에 lim (n->inf.) f(n)/g(n) 유한합니다.

lim (n->inf.) ((2^n + n^2 + n) / 2^n)

inf/inf, an 불확실한 형태, 당신이 사용할 수있는 L 'Hopital의 규칙 작업 할 수있는 무언가를 얻을 때까지 분자와 분모를 구별하십시오.

lim (n->inf.) ((ln(2)*2^n + 2n + 1) / (ln(2)*2^n))
lim (n->inf.) ((ln(2)*ln(2)*2^n + 2) / (ln(2)*ln(2)*2^n))
lim (n->inf.) ((ln(2)*ln(2)*ln(2)*2^n) / (ln(2)*ln(2)*ln(2)*2^n))

한계는 1입니다 2^n + n^2 + n 참으로 O(2^n).

Answer 2

참조하십시오 :

큰 O 표기법 숙제-코드 조각 조각 알고리즘 분석?

큰 O, 어떻게 계산/근사입니까?

누군가 Big-O와 Little-O 표기법의 차이점을 설명해 주시겠습니까?

8 살짜리 아이를위한 big-o? (모욕적이지 않음)