로그의 합계의 큰 $ O $ 표기법은 무엇입니까?

Question

: $$ \ sum ^ {n + m} _ {i= n} \ log (i) $$ 나는 큰 o 표기법이 무엇인지 궁금해하고 어떻게 증명하는 방법을 궁금해하고 있습니다 ... 나는 또한 이것을 그렇게 쓸 수 있다고 믿습니다 $$ \ log (n) + \ log (n + 1) + 로그 (n + 2) + \ ldots + \ log (n + m) $$

또한 $$ \ log (n + m)! / \ log (n-1)! $$

감사합니다

Answer 1

$ \ log $ 의 합이 $ \ log $ 과 동일하다는 것을 호출합니다 제품의.

그런 :

$$ \ log (xy)=log x + \ log y $$

따라서 기능을 변경할 수 있습니다 :

$$ \ begin {정렬} \ sum_ {i= n} ^ {n + m} \ log i &=log \ prod_ {i= n} ^ {n + m} i \\ &=log (n \ cdot (n + 1) \ cdot (n + 2) \ cdot \ ldots \ cdot (m-1) \ cdot m) \\ &=log (m! \ / \ (n-1)!) \\ \ end {정렬} $$

다음은 유사하게 나누기 규칙을 사용하여 이들을 얻을 수 있습니다 :

$$ \ log (m! \ / \ (n-1)!)=log (m!) - \ log ((n-1)!) $$

스털링의 근사치

$$ \ log (m!) - \ log ((n-1)!)= o (m \ log m) $$

더 정확한 경계를 가져 가면 더 잘 수행 할 수 있습니다 :

$$ \ begin {정렬} \ log (m!) - \ log ((n-1)!) & \ leq {1} {2}} e ^ {- m} - \ sqrt {2 \ pi} (n -1) ^ {n- \ frac {1} {2}} e ^ {1-n} \\ &= vdots. \ end {정렬} $$

Answer 2

o ((m +1) 로그 (n + m)).분명히 상한이 있습니다.그러나 대부분의 값에는 최대 값에 가까운 로그가 있으므로 좋습니다.

특히 간단한 경우, 스털링 포뮬라는 더 나은 결과를 줄 수 있지만 Big-O 만 요청합니다.