[algorithm] log (n!) = Θ (n · log (n))입니까?
나는 log ( n !) = Θ ( n · log ( n )) 을 보여 주어야합니다 .
n n으로 상한을 표시하고 ( n / 2) ( n / 2)로 하한을 표시해야한다는 힌트가 주어졌습니다 . 이것은 나에게 직관적이지 않은 것 같습니다. 왜 그런가요? n 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).
결과를 설정하기 위해 전체 로그를 가져옵니다.
답변
죄송합니다. stackoverflow에서 LaTeX 구문을 사용하는 방법을 모르겠습니다.
답변
답변
하한의 경우
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
