lg (n!) 시간에 실행되는 알고리즘의 시간 복잡도

lg (n!) 시간에 실행되는 알고리즘의 Big-Θ (또는 가장 작은 Big-O) 시간 복잡도 란 무엇입니까?lg (n!) 시간에 실행되는 알고리즘의 시간 복잡도

- 당신은 같은 lg(n!) 쓸 수

2014-11-20 Kent

을 가지고있다. 하지만 숙제에서 좀 더 간단한 형태로 작업하도록 요청 받았을 것입니다. 이것은'log (ab) = log (a) + log (b)'를 아는 것이 매우 쉽습니다. (그리고 아니오, 숙제에 대답하지 않을 것입니다.). – Shahbaz

숙제와는 아무런 관련이 없습니다. 나는 P 대 NP 문제를보고, 왜 * 내 알고리즘이 그런지를 결정하려고 노력하고있다. ~ O (2^n) – Kent

기본적으로 O (lg (n!))가 O (2^n)인지 궁금합니다. – Kent

(LG 곳> 로그베이스 2) : 지금

enter image description here

을 그리고 당신은 적분으로 근사 할 수

enter image description here

마지막으로 적분을 해결하십시오 :

enter image description here

16,그리고 당신의 대답은 :

enter image description here

lg(n!)

그것은`Θ (! N LG 전자())`의 O(nlog(n)) 복잡성

출처

2014-11-20 16:50:57 Everettss

또는 (n/2)^(n/2) <= n! <= n^n. – tmyklebu

답변