[algorithm] log (n!) = Θ (n · log (n))입니까?

나는 log ( n !) = Θ ( n · log ( n )) 을 보여 주어야합니다 .

n n으로 상한을 표시하고 ( n / 2) ( n / 2)로 하한을 표시해야한다는 힌트가 주어졌습니다 . 이것은 나에게 직관적이지 않은 것 같습니다. 왜 그런가요? n nn · log ( n ) 로 변환하는 방법 (즉 방정식의 양변을 로그 하는 방법)을 확실히 볼 수 있지만, 역으로 작동합니다.

이 문제를 해결하는 올바른 방법은 무엇입니까? 재귀 트리를 그려야합니까? 이것에 대해 재귀가 없으므로 가능한 접근 방식처럼 보이지 않습니다.



답변

기억

log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)

당신은에 의해 상한을 얻을 수 있습니다

log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)
                                = n*log(n)

그리고 합계의 전반부를 버리고 비슷한 일을함으로써 하한을 얻을 수 있습니다.

log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n)
                                       = log(n/2) + log(n/2+1) + ... + log(n-1) + log(n)
                                       >= log(n/2) + ... + log(n/2)
                                        = n/2 * log(n/2)


답변

나는 이것이 받아 들일 수있는 대답이있는 매우 오래된 질문이라는 것을 알고 있지만 실제로는 힌트에서 제안한 접근법을 사용하지 않습니다.

꽤 간단한 주장입니다.

n!(= 1 * 2 * 3 * … * n)은 n각각보다 작거나 같은 숫자 의 곱입니다 n. 그러므로 그것은 n모두 같은 수 의 곱보다 작습니다 n. 즉 n^n.

제품 n/2에서 숫자의 절반 (즉, 숫자) n!이보다 크거나 같습니다 n/2. 그러므로 그들의 곱은 n/2모두 같은 곱의 곱보다 큽니다 n/2. 즉 (n/2)^(n/2).

결과를 설정하기 위해 전체 로그를 가져옵니다.


답변

여기에 이미지 설명을 입력하십시오

죄송합니다. stackoverflow에서 LaTeX 구문을 사용하는 방법을 모르겠습니다.


답변

스털링의 근사 참조 :

ln (n!) = n * ln (n)-n + O (ln (n))

마지막 두 용어는 첫 번째 용어보다 덜 중요합니다.


답변

하한의 경우

lg(n!) = lg(n)+lg(n-1)+...+lg(n/2)+...+lg2+lg1
       >= lg(n/2)+lg(n/2)+...+lg(n/2)+ ((n-1)/2) lg 2 (leave last term lg1(=0); replace first n/2 terms as lg(n/2); replace last (n-1)/2 terms as lg2 which will make cancellation easier later)
       = n/2 lg(n/2) + (n/2) lg 2 - 1/2 lg 2
       = n/2 lg n - (n/2)(lg 2) + n/2 - 1/2
       = n/2 lg n - 1/2

lg (n!)> = (1/2) (n lg n-1)

두 경계를 결합 :

1/2 (n lg n-1) <= lg (n!) <= n lg n

(1/2)보다 큰 하한 상수를 선택하면 브래킷 내부의 -1을 보상 할 수 있습니다.

따라서 lg (n!) = Theta (n lg n)


답변

Mick Sharpe가 당신을 떠난 곳에서 더 당신을 돕기 :

탈선은 매우 간단합니다. http://en.wikipedia.org/wiki/Logarithm- > Group Theory를 참조하십시오 .

log (n!) = log (n * (n-1) * (n-2) * … * 2 * 1) = log (n) + log (n-1) + … + log (2 ) + 로그 (1)

n을 무한히 큰 것으로 생각하십시오 . 무한 빼기 1이란 무엇입니까? 또는 빼기 2? 기타

log (inf) + log (inf) + log (inf) + … = inf * log (inf)

그런 다음 inf 를 n으로 생각하십시오 .


답변

고맙지 만 답이 설득력이 있지만 내 경우에는 Θ 속성을 사용해야합니다 .

log(n!) = Θ(n·log n) =>  log(n!) = O(n log n) and log(n!) = Ω(n log n)

이 웹에서 발견 한 문제를 확인하기 위해 모든 프로세스를 설명했습니다 : http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm