문제
2^n + 6n^2 + 3n
나는 그것이 가장 높은 순서 용어를 사용하는 O (2^n) 일 뿐이라고 생각하지만, 이것을 증명하는 공식적인 접근법은 무엇입니까?
해결책
당신은 그것을 증명할 수 있습니다 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)
.
다른 팁
제휴하지 않습니다 StackOverflow