내 마지막 공부를위한 공부 : 점근 표기법

Question

현재 최종 결정 알고리즘을 공부 중입니다. 이것은 숙제 문제가 아니며 오래된 최종 시험에서 나옵니다.

Show that f(n) = 4logn + log log n is big theta of logn. 

로그 로그 n은 로그 n보다 상당히 작으므로 중요하지 않습니다. 하지만 공식적으로 어떻게 표현할 수 있습니까? 저는 한계와 L' hopital에 대해 잘 알고 있으므로 저에게 그 방법으로 어떻게하는지 보여 줄 수 있다면 고맙겠습니다.

Answer 1

빅 세타의 정의를 기억하십시오. 함수 f(x) 당신은 f(x) = 4*log(x) + log(log(x)) 및 g(x) = log(x)이 Theta(g(x))

경우입니다. 이제 조건을 만족하는 c_0, c_1 및 x_0에 대한 값이 있음을 보여 주어야합니다. 그것은 아주 쉽게,

우리는 c_0 = 1 및 log(log(x_0)) > 0 충분히 큰 x_0 걸릴 경우 (정확한 번호가 대수의 기초에 따라 다르지만 같은 번호가 항상있다, 우리는 정말 알 필요가 없습니다) (힌트 log(x) <= 4*log(x) + log(log(x)) : 모든 x > x_0에 대한 최초의 불평등이 사실임을 표시합니다. log(log(x)) 이미 > 0이며, 로그 함수가 단조 증가하고있다

을 이제 c_1 = 5를 선택할 수 있도록 두 번째 불평등 지금

에 단순화, 4*log(x) + log(log(x)) <= 5*log(x)된다.

log(log(x)) <= log(x) 

모두 x > x_0입니다. 그 증거를 운동으로 남겨 두겠습니다. :-)

Answer 2

쉬운 방법으로 c1, c2 및 no를 찾는 방법.

상단 바운드 찾기 :

f(n) = 4logn+loglogn 


    For all sufficience value of n>=2 

     4logn <= 4 logn 
     loglogn <= logn 

    Thus , 

    f(n) = 4logn+loglogn <= 4logn+logn 
          <= 5logn 
          = O(logn)  // where c1 can be 5 and n0 =2 

하한 찾기 :

f(n) = 4logn+loglogn 

    For all sufficience value of n>=2 

     f(n) = 4logn+loglogn >= logn 
    Thus,    f(n) = Ω(logn) // where c2 can be 1 and n0=2 


    so , 
         f(n) = Ɵ(logn)