빅 오 질문 - 알고리즘 분석

Question

나는 시험을 위해 개정 중이며 인터넷에서이 문제를 발견하고 해결 방법에 대해 궁금해하고 있습니다. (베이스 2 로그)

그 로그 (2 N)를 증명은 O의 부재 ( N 로그)이다.

나는 그것을 풀어 줬지만 아무런 대답도 제시되지 않았으므로 나는 옳은지 확실치 않습니다. 도와 주실 수 있겠습니까? 여기

내 시도 :

로그 2 N- C 로그 N ≤ 0
로그 2 + 로그 N- C 로그 N ≤ 0
1 + (1-c) 로그 n이하 제로 N = 8, C = 10 평가 : 0 37,≤
는

예. (I는 로그 N으로 나눈). 따라서 사실입니다.

내 질문은 :

1. 오전 나는이 권리를거야?

2. 내 대답을 더 단순화 할 수 있습니까?

Answer 1

긴 대답은 한계 두 함수의 비율 (즉,이 묶여) 존재

   log(2n)  log(2) + log(n)  log(2) 
lim n->infinity ------- = lim --------------- = lim ------ + 1 = 0 + 1 = 1 
       log(n)  log(n)    log(n) 

때문에, 그들은 동일한 점근 복잡도를 가지고있다. 같은 방법으로

, 그 O를 증명하기는 (N ²)는 O (n)이, 당신이 대 O (N 로그) (n)이 O를 위해 이렇게

lim n->infinity (n^2/n) = lim n which tends to infinity 

할 것 아니다

lim n->infinity (n/log n) 

이 어떻게 든 처리되어야하기 때문에 더 많은 작업이 필요합니다. 따라서 트릭은 파생 상품을 대신 사용할 수 있다는 것입니다. 한계의 파생 상품도 점근 적으로 관련되어야합니다 (그렇지 않으면 적분은 원래 함수가 아닙니다).당신은 1 N의 미분을 가지고 가고,

lim n->infinity (1/(1/n)) = lim n which tends to infinity 

Answer 2

lg(2n) = lg(2) + lg(n).

LG (2)는 일정하다. 위키 백과, Logarithmic identities을 참조하십시오.