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

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

---

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

n ^n으로 상한을 표시하고 ( n / 2) ^{( n / 2)로} 하한을 표시해야한다는 힌트가 주어졌습니다 . 이것은 나에게 직관적이지 않은 것 같습니다. 왜 그런가요? n ⁿ 을 n · 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).

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

---

스털링의 근사 참조 :

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)

---

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

---

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

It's deriveration is quite simple: see 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) + log(1)

Think of n as infinitly big. What is infinite minus one? or minus two? etc.

log(inf) + log(inf) + log(inf) + ... = inf * log(inf)

And then think of inf as n.

---

Thanks, I found your answers convincing but in my case, I must use the Θ properties:

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

to verify the problem I found this web, where you have all the process explained: http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm

---

This might help:

eln(x) = x

and

(l m ) n = l m * n

---

http://en.wikipedia.org/wiki/Stirling%27s_approximation 스털링 근사가 도움이 될 수 있습니다. 10 ^ 10 이상의 거대한 수와 관련된 계승 문제를 처리하는 데 실제로 도움이됩니다.

참고 URL : https://stackoverflow.com/questions/2095395/is-logn-%ce%98n-logn