나는 asymptotic 분석에 관한 문제를 연습하고 있는데, 나는이 문제를 고집하고있다.log (n!) = O ((log (n))^2)입니까?
은 log(n!) = O((log(n))^2)입니까?
나는
log(n!) = O(n*log(n))
(log 1 + log 2 + .. + log n <= log n + log n + ... + log n)
및
(log(n))^2 = O(n*log(n))
(log n <= n => (log n)^2 <= n*logn)
나는 더 이상 진행 할 수없는임을 보여줄 수입니다. 더 나아가는 방법에 대한 힌트 또는 직감? 감사
Stirling's Approximation에 Accoriding :
log(n!) = n*log(n) - n + O(log(n))
O(nlogn)
것이다 log(n!) 행
:
log(1) + ... + log(n/2) + ... + log(n) = log(n/2) + ... + log(n) = log(n/2) + ... + log(n/2) = n/2 * log(n/2)
그래서 낮은 바운드도 nlogn입니다. 분명히 대답은 입니다.
그게 질문이 아니 었습니다! –
'log (n!) = O ((log (n))^2)?'대답은 NO @JanakyMurthy –
@JanakyMurthy 어떤 종류의 대답을 기대합니까? –
나는 내 자신의 질문에 대한 답을 얻었습니다. 우리는 다음과 같은 사실을 증명합니다 : (log(n))^2
3) n*log(n)에 대한
1) n*log(n)이 꽉 log(n!)
2) n*log(n)에 대한 바인딩이 상한 것은 (log(n))^2
(1)에 대한 증명은 this을 참조하십시오.
증명 (2) & (3)은 질문 자체에서 제공됩니다. 성장 속도 log n< 성장 속도 n. 그래서 성장 속도 log(n)^2< 성장률은 n*log(n)입니다. 그래서 여기 log(n)^2 = o(n*log(n)) (나는 n*log(n)의 성장률을 나타 내기 위해 작은-O를 사용하고 그래서 결론은 내가 어떤 실수하는 일
당신에 의해 주어진 링크에서 증명 3에 대한 접근은 하한에 대한 내 접근법과 동일하며, 그의 하한값은'n/2 * log (n/2)'@ 자나키 –
을 한 경우
log(n!) = big-omega(log(n^2))저를 수정한다는 것입니다log(n)^2의 성장 속도보다 확실히 큰 사실은 log (n!)이 O ((log n)^2)에 없다는 것입니다. – Henry
이 질문은 프로그래밍 알고리즘이 아니라 수학에 관한 것입니다. – FDavidov
@Henry 그러면 어떻게 표시 할 수 있습니까? 그래프를 플로팅하는 것보다 더 공식적인 방법이 있다는 것을 보여줄 수 있습니까? –